Integer Break
找规律:
| n | max |
|---|---|
| 3 | 2*1 |
| 4 | 2*2 |
| 5 | 3*2 |
| 6 | 3*3 |
| 7 | 3*4 |
| 8 | 3*5=3*(3*2) |
| 9 | 3*3*3 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
public class Solution { public int integerBreak(int n) { if(n == 2) return 1; if(n == 3) return 2; if(n == 4) return 4; int[] dp = new int[n+1]; dp[0] = 0; dp[1] = 1; dp[2] = 1; dp[3] = 2; dp[4] = 4; for(int i = 5; i <=n; i++) { dp[i] = 3*Math.max((i-3),dp[i-3]); } return dp[n]; } } |
Leave A Comment