Closed KivenGood closed 3 years ago
也就是题目416中的非压缩算法存在问题，j循环时未考虑比nums[i-1]小的问题。 for (int i = 1; i <= n; ++i) { for (int j = nums[i-1]; j <= target; ++j) { dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]]; } } 测试用例：[1,5,10,6],应该是true，使用此代码是false； 压缩空间的算法是正确的。
感谢,下个版本会更正
changgyhub
commented
3 years ago changgyhub
commented
3 years ago
也就是题目416中的非压缩算法存在问题，j循环时未考虑比nums[i-1]小的问题。 for (int i = 1; i <= n; ++i) { for (int j = nums[i-1]; j <= target; ++j) { dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]]; } } 测试用例：[1,5,10,6],应该是true，使用此代码是false；
压缩空间的算法是正确的。