如何將此二維DP（動態程序）解決方案優化爲一維？

Question

以下頁面包含一個2-d 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]; 

我試圖通過更換，以減少佔用空間2-D陣列瓦特/一個像這樣的一維：

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

解決方案的拓撲排序不正確。

如果將第二個循環更改爲for (int j = sum; j >= 1; j--)它應該可以工作。

發生這種情況的原因是，當您在第二個循環中向前移動時，您也正在考慮通過current index i解決的解決方案，因此在解決方案中多次包括當前元素，而不是僅包含一次。