LeetCode 343.整数拆分
1.题目要求:
2.题目代码:
class Solution {
public:
int integerBreak(int n) {
//先确定dp数组
vector<int> dp;
//1.确定dp数组的含义
//2.确定dp的递推公式
//3.初始化dp数组
//4.遍历顺序
dp.resize(n + 1);
dp[0] = 0;
dp[1] = 0;
dp[2] = 1;
for(int i = 3;i <= n;i++){
for(int j = 1;j < i;j++){
vector<int> array;
array.push_back(j * (i - j));
array.push_back(j * dp[i - j]);
array.push_back(dp[i]);
vector<int> :: iterator it = max_element(array.begin(),array.end());
dp[i] = *it;
}
}
return dp[n];
}
};