algorithm - 子集和的DP解的空间优化?
问题描述
我正在为正数做子集和问题。在典型的 DP 解决方案中,我们使用表格 table[n+1][sum+1] 的 2D DP 表,其中 n 是集合中元素的数量,并且sum
是目标总和。现在我想优化它以仅使用一行,因为所有行都使用前一行的结果。为此,我提出了一个解决方案:
boolean DP[] = new boolean[sum+1];
DP[0] = true;
for(int i = 0; i < arr.length; i++) {
for(int j = arr[i]; j <= sum; j++) {
DP[j] = DP[j] || DP[j-arr[i]];
}
}
return DP[sum];
此代码未通过某些测试用例。但是,如果我将内部循环更改为向后迭代:
for(int j = sum; j >= arr[i]; j--)
然后这段代码通过了所有的测试用例。我无法弄清楚向后迭代所产生的差异。我会很感激解释。
解决方案
简单的例子来帮助你理解
arr = {1, 4}, sum = 7
在向前迭代的情况下,第一次迭代,i = 0
dp[0] = true
for (int j = arr[0]; j <= sum; j++){
}
这是此循环中的步骤:
dp[1] = dp[1] || dp[1 - 1]; //true as dp[0] = true
dp[2] = dp[2] || dp[2 - 1]; // also true, as previous step, we update dp[1] = true
....
dp[7] = dp[7] || dp[7 - 1]; // true for similar reason
所以,对于第一次迭代,所有元素都是真的
在向后迭代的情况下,第一次迭代,i = 0
dp[0] = true
for (int j = sum; j >= arr[0]; j--){
}
这是此循环中的步骤:
dp[7] = dp[7] || dp[7 - 1]; //false
dp[6] = dp[6] || dp[6 - 1]; // also false,
....
dp[1] = dp[1] || dp[1 - 1]; // true as dp[0] = true
所以,对于第一次迭代,除了dp[1]
and之外dp[0] = true
,这就是我们想要的。
推荐阅读
- ubuntu-16.04 - Zabbix 从 4.0.21 升级到 5.2 mysqlversion 错误
- c# - 在字节中间设置 3 位 C#(按位运算符)
- javascript - 如何对所有列表(数组)项目进行操作?
- reactjs - React:如何填充保存在本地存储中的数据?
- javascript - 将 Lua toNumber 与 JS parseInt 进行比较 - 结果不匹配
- javascript - 在 Sharepoint 中的异步查询中委托函数
- c - “函数‘fizzbuzz’的参数太少”?
- windows - 来自 qt 框架安装程序的 Windows 安装程序无法在詹金斯管道中运行
- flutter - 列表中的一组收音机颤动
- c# - 返回 OData 中的派生类型