https://leetcode.cn/problems/integer-break/
dp,思路较为巧妙,需要考虑一个数至少能拆成两份这个点,且需要考虑到拆的这个数的值域是多少(1,i-1)
且选择拆一次还是拆多次
class Solution {
public:
int integerBreak(int n) {
// f[i]表示拆分i成若干个整数的最大乘积
// f[i] = max(j*(i-j),j*f[i-j])
// f[2]=1;
const int N = 60;
int f[N];
memset(f,0,sizeof f);
f[2]=1;
for(int i=3;i<=n;i++)
for(int j=1;j<i;j++)
f[i]=max(f[i],max(j*(i-j),j*f[i-j]));
return f[n];
}
};
标签:cn,int,整数,拆分,343,leetcode From: https://www.cnblogs.com/lxl-233/p/18390909