C++(动态规划之拆分整数)

其实我交上去都有点似懂非懂

题目：（343. 整数拆分 - 力扣（LeetCode））

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

示例 1:

输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

提示:

• 2 <= n <= 58

题解：

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1);
        dp[2]=1;
        for(int i=3;i<=n;i++){
            for(int j=1;j<=i;j++){
                dp[i]=max(dp[i],max((i-j)*j,dp[i-j]*j));
            }
        }
        return dp[n];
    }
};

 理解：

首先解释一下这个动态规划数组的含义：数字i能得到的最大乘积，所以当i=2的时候初始化为1(也就是2能拆出最大的乘积是1*1的时候)。剩下的我感觉我有点解释不出来，能力有限（过段时间回顾这篇博客的时候能解释的好就补在评论区）