memoizationをサブセット合計に追加するには？

Question

私は再帰的な解法を使って部分集合和問題を解決しようとしていますが、もう少し効率的にするために、私はそれにメモを入れようとしています。しかし、メモのないコードは正しい解決策を示しますが、メモを付けると正しく機能しません。

public int subsetSum(int num[], int idx, int expecedSum, int dp[]) { 
    if (expecedSum == 0) { 
     return 1; 
    } 
    else if (idx < 0 || expecedSum < 0) { 
     return 0; 
    } 
    else { 
     if (dp[expecedSum] == -1) { 
      int x = subsetSum(num, idx - 1, expecedSum, dp); 
      int y = subsetSum(num, idx - 1, expecedSum - num[idx], dp); 
      dp[expecedSum] = (x == 1 || y == 1) ? 1 : 0; 
     } 
     return dp[expecedSum]; 
    } 
} 

public static void main(String args[]) { 
    Solution s = new Solution(); 
    int num[] = new int[]{1, 2, 3, 4, 5, 6, 7}; 
    int sum = 0; 
    int n = new Scanner(System.in).nextInt(); 
    int dp[] = new int[n + 1]; 
    for (int i = 0; i < dp.length; i++) { 
     dp[i] = -1; 
    } 

    dp[0] = 1; 
    s.subsetSum(num, num.length - 1, n, dp); 

} 

なぜこれが機能しないのかを教えてもらえますか？

Iは入力N = 14次に、理想的にはDP場合[14] 1が含まれていなければならないが、それは1

Answer 1

和状態を記述するのに十分ではないが含まれていません。ペア（合計、インデックス）はです。 dpに配列(max_sum + 1) x num.lengthの配列を作成し、メソッドで(idx, expectedSum)のペアのメモを適用すると動作します。