【力扣】刷题备忘录-动归-343. 整数拆分

本文主要是介绍【力扣】刷题备忘录-动归-343. 整数拆分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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];}
};

这题难点在于想到有两种可能的来源一个是当前拆分后直接相乘的结果另一个是拆出来的数字对应到dp table上的解相乘的结果
优化点在于想到拆分相乘的时候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];}
};