动态规划 - 在数组中查找目标求和方式

Question

我在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？我知道如果向上计数，结果会比答案大得多，但我无法弄清楚向上计数的本质问题。

任何帮助不胜感激！

Answer 1

由于nums[i]保证为正数，因此在以下行中：

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

数组中较大索引处的

元素正在根据同一数组中较小索引处的元素值进行修改。

由于j开始时为高并递减，因此在每次迭代中，可以保证需要读取的值(索引小于 j(不是已覆盖的值(大于 j 的索引(。

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

在就地对数组进行操作的算法中，这种事情是一个非常常见的考虑因素。

Answer 2

当第二个循环向下计数时，您计算所有可能性，以求和数组的元素并获得目标S其中数组的每个元素只能取一次。但是，当第二个循环向上计数时，您会计算数组的每个元素都可以被任意次数获取的可能性。所以第二个数字大于或等于第一个数字。