343. 整數拆分

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 - 1; j++){ // 這里j的最大值去到i-2就可以，這時i - j = 2 正好能用初始化的值dp[i] = max(dp[i], max(j * dp[i - j], j * (i - j))); // 1. 執行拆分 有兩種可能的來源 //2. 還要和dp[i]去比 然后更新// std::cout << "i的當前值是：" << i << std::endl;// std::cout << "dp i的當前值是：" << dp[i] << std::endl;}}return dp[n];}
};

1. 這題難點在于想到 有兩種可能的來源 一個是當前拆分后直接相乘的結果 另一個是拆出來的數字對應到dp table上的解相乘的結果
2. 優化點在于想到 拆分相乘的時候j不需要去查dp[j]。

• 至于原因，代碼隨想錄給的是因為拆分j的情況，在遍歷j = 1 to i -2 的過程中都考慮到了。
• 我認為還有一個解釋是，把這個求解過程展開，比如，dp[5] = 2 × 3, dp[6] = 3 × 3等，就會發現其實最大值都是由2 3組成的。所以把代碼又優化成了下面這樣：

class Solution {
public:int integerBreak(int n) {if (n <= 3) return n -1; // 這里要記得處理,不然當n<=3的時候，循環里面dp[4]取不到值 會報錯vector<int> dp(n+1);dp[2] = 1;dp[3] = 2;for (int i = 4; i <= n; i++) {for (int j = 1; j <= 3; j++){  // 這里只用考慮j <= 3的情況dp[i] = max(dp[i], max(j * dp[i - j], j * (i - j))); }}return dp[n];}
};

其實分析到這里也可以寫貪心了，但二刷的事情就留給二刷去做吧，這個優化方案其實已經不是動歸本身了，而是基于數學做的改進了。