动态编程 - 在数组中查找目标求和方式

我在leetcode中遇到了一个问题,我看了其他使用DP的解决方案,但有一些我无法理解的东西,希望你能给我一些提示 .

问题是:给定一个只包含正整数的非空数组,找到选择其总和等于目标S的一些整数的方法 .

解决方案是:

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向下计数到nums [i],但为什么它不能从nums [i]向上计数到S?我知道如果向上计数,结果会比答案大得多,但我无法弄清楚向上计数的本质问题 .

任何帮助表示赞赏!

回答(2)

2 years ago

由于 nums[i] 保证是正数,因此在行中:

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

基于同一数组中较小索引处的元素的值,正在修改较大索引处的数组的元素 .

因为 j 启动高并递减,所以在每次迭代中,保证您需要读取的值(索引小于j)不是您已经覆盖的值(索引大于j) .

相反,如果你开始 j 低并递增它,那么你最终会覆盖稍后将在循环中读取的值 . 然后它们将具有不正确的值并产生错误的答案 .

对于在阵列上运行的算法,这类事情是一个非常普遍的考虑因素 .

2 years ago

当第二个循环向下计数时,您将计算所有可能的数组元素并获得目标 S ,其中数组的每个元素只能被采用一次 . 但是当第二个循环向上计数时,你可以计算出阵列的每个元素都可以被任意次取的可能性 . 所以第二个数字大于或等于第一个数字 .