Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.
Example 1:
Input: 2 Output: 1 Explanation: 2 = 1 + 1, 1 × 1 = 1.
Example 2:
Input: 10 Output: 36 Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.
Note: You may assume that n is not less than 2 and not larger than 58.
A:
DP
就是当分解的时候, 前面几个,其实是,分解成最少1个positive integer的时候的解
class Solution { public: int integerBreak(int n) { if(n<=2) return 1; if(n==3) return 2; vector<int> V(n+1,0); // max value if at least ONE positive integer V[1] = 1; V[2] = 2; V[3] = 3; for(int i=3; i< n+1; i++) { for(int j = 1;j<i;j++){ V[i] = max(V[i], V[j] * (i-j)); } } return V[n]; } };
No comments:
Post a Comment