343. 整数拆分(leetcode)

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];}
};