LeetCode 343 整数分割
🟡 中等
https://leetcode.cn/problems/integer-break/
递归
首先思考递归，如果递归函数语义是问题本身，那么与子问题的联系为：本层的返回值=分出来的一个数*右边的数分割得到的最大乘积。
class Solution {
public:
int integerBreak(int n) {
if(n<=2) return 1;
int max_ret = 0;
for(int i = 1;i<n;i++){
max_ret = max(max_ret,i*integerBreak(n-i));
}
return max_ret;
}
};
但是这是错误的，因为右边可以不分，这样可能会最大，例如：如果右边为3，此时右边不分最大，如果分最大为1*2 = 2，结果倒小了。
所以判断一下右边是分了大还是不分大。
class Solution {
public:
int integerBreak(int n) {
if(n<=2) return 1;
int max_ret = 0;
for(int i = 1;i<n;i++){
int right =integerBreak(n-i)>n-i?integerBreak(n-i):n-i;
max_ret = max(max_ret,i*right);
}
return max_ret;
}
};
动态规划
class Solution {
public:
// if (n <= 2)
// return 1;
// int max_ret = 0;
// for (int i = 1; i < n; i++) {
// int right = integerBreak(n - i) > n - i ? integerBreak(n - i) : n - i;
// max_ret = max(max_ret, i * right);
// }
// return max_ret;
int integerBreak(int n) {
int dp[n+1];
memset(dp,0,sizeof dp);
dp[1] = 1;
dp[2] = 1;
for(int i = 3;i<=n;i++){
for(int left =1;left<=i-1;left++ ){
int right = max(dp[i-left],i-left);
dp[i] = max(dp[i],left*right);
}
}
return dp[n];
}
};