java - 如何将此二维 DP(动态程序)解决方案优化为一维？

Question

下一页包含“子集和”问题的二维 DP 解决方案:

https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/SubsetSum.java

核心方法:

boolean[][] T = new boolean[input.length + 1][total + 1];
for (int i = 0; i <= input.length; i++) {
    T[i][0] = true;
}

for (int i = 1; i <= input.length; i++) {
    for (int j = 1; j <= total; j++) {
        if (j - input[i - 1] >= 0) {
            T[i][j] = T[i - 1][j] || T[i - 1][j - input[i - 1]];
        } else {
            T[i][j] = T[i-1][j];
        }
    }
}
return T[input.length][total];

我试图通过用这样的一维数组替换二维数组来减少空间使用:

boolean[] T = new boolean[sum + 1];     
T[0] = true;      

for (int i = 1; i <= input.length; i++) {
    for (int j = 1; j <= sum; j++) {
        if (j - input[i - 1] >= 0) {
            T[j] = T[j] | T[j - input[i - 1]]; //not using ||
        } 
    }
}
return T[sum];

我悲惨地失败了:它对任何输入都返回 true。有人可以指出问题吗？

Answer 1

The Topological ordering of your solution is incorrect.

如果将第二个循环更改为 for (int j = sum; j >= 1; j--)，它应该可以工作。

发生这种情况是因为当您在第二个循环中向前移动时，您也在考虑由当前索引 i 解决的解决方案，因此在解决方案中多次包含当前元素，而不是仅包含一次。