動的プログラミング - 配列のターゲットの総和を見つける

Question

私はleetcodeに問題が発生しました。私はDPを使用した他のソリューションを見ましたが、理解できないものがあります。

ある問題：

int findTargetSumWays(vector<int>& nums, int S) 
{ 
    int n = nums.size(); 
    vector<int> dp(S+1, 0); 

    dp[0] = 1; 
    for(int i=0; i<n; i++) 
     for(int j=S; j>=nums[i]; j--) 
     //for(int j=nums[i]; j<=S; j++) //why it is wrong? 
     { 

      dp[j] += dp[j-nums[i]]; 
     } 
    return dp[S]; 
} 

：、その合計等しいS.

を対象とするソリューションがあるこれらの整数の一部を選択する方法を多くの方法を見つけるだけ正の整数を含む非空の配列を考えます

コードでは、2番目のループはSからnums [i]までカウントしますが、なぜnums [i]からSまでカウントできないのですか？私は上向きにカウントすれば、結果は答えよりはるかに大きくなることは知っていますが、上向きにカウントする自然の問題を理解することはできません。

ご了承ください。

Answer 1

同じ配列内にあります。

jは、すべての反復で高く開始され、デクリメントされるため、（jより小さいインデックスの）値は、すでに上書きされた値（jより大きいインデックス）でないことが保証されます。

代わりにjをローにしてインクリメントすると、後でループで読む値を上書きしてしまいます。彼らは間違った値を持ち、間違った答えを生み出します。

このようなことは、アレイ上で動作するアルゴリズムでは非常に一般的な考慮事項です。

Answer 2

2番目のループがカウントダウンするとき、arrayの要素を合計してarrayを得るすべての可能性を数えます。ここで、配列の各要素は1回だけ取り出すことができます。しかし、2番目のループが上向きになると、配列のすべての要素を何回でも取ることができる可能性が得られます。 したがって、2番目の番号は最初の番号以上です。

dp[j] += dp[j-nums[i]] 

配列の要素大きい指数が小さいインデックスの要素の値に基づいて変更される時：nums[i]が一列に、陽性であることが保証されているので