343. 整数拆分

Problem: [343. 整数拆分](https://leetcode.cn/problems/integer-break/description/)

思路

其实这道题目的解法之前一直没有看明白。

主要是要搞清楚dp数组的含义：拆分i得到的最大值。

递推公式：dp[i] = max(i * dp[i-j],i * (i -j), dp[j])

初始化：0、1、2我们可以直接写出来0、0、1

递推顺序：从3以后开始，是两层循环，因为要对i进行j次拆分取得最大值

其实这里这个dp[i] = max(i * dp[i-j],i * (i -j), dp[j])dp【j】我还是不太明白

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]

class Solution {

public:

    int integerBreak(int n) {

        vector<int> dp(n + 1);

        dp[0] = 0;

        dp[1] = 0;

        dp[2] = 1;

        for (int i = 3; i < n + 1; i++) {

            for (int j = 1; j <= i/2; j++) {

                dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));

            }

        }

        return dp[n];

    }

};