今日最新！LeetCode刷题：343. 整数拆分的完全背包写法解析

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

今日最新！LeetCode刷题：343. 整数拆分的完全背包写法解析

2023-01-17 19:57:09 来源：博客园

【资料图】

dp的含义表示：从前i个数中挑选，满足和为j的最大乘积为多少。由于是乘积所以dp初始均为1。i为2开始是因为从1开始挑选，j为2开始应为有效数字是从2开始。进一步空间优化，应为dp[i][j]只与其相邻的状态有关。

// 思路初探：将本题转化成完全背包问题。// 完全背包问题不用塞满背包，而本题“必须塞满背包”，如何转化// 如果塞不满，那么塞不满的部分就取数字1，由于 n x 1 = n，所以不影响最终结果// 集合：dp[i][j]表示表示考虑数字1~i情况下，数字和≤j情况下的乘积// 属性：乘积最大值// 状态转移方程：dp[i][j] = max(dp[i -1][j], dp[i][j - i] *i,dp[i][j-2i]*i*i)// 怎么代码简化上述状态转移方程参考acwing的完全背包问题class Solution {public:    int integerBreak(int n) {        if(n == 2){            return 1;        }        if(n == 3){            return 2;        }        vector> dp(n+10,vector(n+10,1));        for(int i = 2;i<=n;i++){            for(int j = 2;j <= n;j++){                dp[i][j] = dp[i-1][j];                if(j >= i){                    dp[i][j] = max(dp[i][j],dp[i][j-i] * i);                    // 这一行很多细节的。                }            }        }        return dp[n][n];    }};

本代码有很多细节：

为何要将全部初始状态赋予1？可能会考虑到初始化可以改成如下也行：

vector> dp(n+10,vector(n+10,0));        for(int j = 2;j<=n;j++){            dp[1][j] = 1;        }

其实是不行的，因为状态更新的时候有：

if(j >= i){                    dp[i][j] = max(dp[i][j],dp[i][j-i] * i);                    // 这一行很多细节的。                }

第一次j==i的时候dp[i][j-i]=dp[i][0]，因此dp[i][0]的初始值也应该赋1。2. 为何要把2和3特殊处理提前返回？以2举例，2的正确答案应该是1，如果不提前返回，那么当进入到dp[i][j] = max(dp[i][j],dp[i][j-i] * i);会出现总和为2，那么可以选择一个2，答案就为2的情况。又因为在其他的选择方式中不存在结果比2大的情况，因此答案错误的输出2。总结来说：对于符合下列条件的数k需要提前返回：\(合法的结果 < k\)。满足此条件的数就是2和3。

为何只有2和3满足不赘述了，有需要再补充。

关键词：背包问题转移方程可以选择