动态规划leetcode 343整数拆分

问题描述

思路

注意事项
此题的有一个坑，，，首先明白函数的定义是：将i分割，获得的最大乘积
但是我们在计算的时候需要考虑不分割的情况，即直接用j*(i-j)

代码

class Solution {
private:
    int max3(int a,int b,int c) 
    {
        return max(a,max(b,c));
    }

public:

    int integerBreak(int n) {
        vector <int> dp(n+1,0);
        dp[2]=1;
        for(int i=3;i<=n;i++) {
            for(int j=1;j<=i-1;j++) {
                dp[i]=max3(dp[i],dp[i-j]*j,j*(i-j));//需要考虑不分割的情况
            }
        }
        return dp[n];
    }
};