leetcode 343 整数拆分 | 动态规划！递推公式有点难想@_@

题目链接：. - 力扣（LeetCode）

这道题目的意思就是给你一个数n，将其拆分为k个整数的和，并且使得这些整数的乘积最大，这道题可以用dp的方法来做

那么这道题我们怎么用dp的方法来想呢，首先肯定还是我们的动规五部曲，首先来确定dp数组的含义，题目的要求是最大的乘积，所以这里我们dp数组的含义代表的就是整数i拆分后所能得到的最大乘积，然后就是然后就是递推公式了，这里的递推公式怎么来求呢，我们这里可以知道的是这个整数可以被拆成两个数以及两个以上的数，那么这里如果是两个以上的数，我们就不好表示了，所以如果是两个以上的数那么另外的数，我们是不是可以用之前已经求出的dp数组的值来表示，因为如果是拆分出来的，就一定比当前的i要小，所以一定已经求出来乘积的最大值了，并且我们dp数组的含义就是拆分后乘积的最大值，所以这里其实也是相当于一种记忆化搜索，那么这样我们就不难写出如下的递推公式：dp[i] = max(j*(i-j),j*dp[i-j]);第一个式子就是代表这拆分成两个数的情况，后面的式子就是代表拆分成多个式子的情况，只不过是在之前就已经计算过，所以直接用就可以了，这里你可能会疑惑，为什么要拆i-j不拆前面的j，你想想，我在for循环遍历的时候，就是以j为基准的，你拆j，不就是相当于以i-j为基准吗，那不是一样的吗，因为他们相加的值相等啊，如果你觉得两个都要拆的话，那不就是默认是要分成四个及以上的数吗，这样也不对啊，你会漏掉两个和三个的情况，所以不需要考虑这种情况，遍历顺序就不用多说了，肯定是从小到大遍历，来看具体代码的实现

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

注意这里每次还要与自己本身取一个最大值，初始化忘记说了，当然是最简单的数，一开始初始化为1，至于0，1初不初始化都无关紧要，这就是我对本题的理解。