Leetcode第494题Target Sum动态规划部分难懂

Question

我发现这个解决方案非常快（超过 99.5%），同时 space-节省（超过 95%）。我了解大部分内容，除了以下行：dp[j]=dp[j]+dp[j-num]

我知道 w 正在计算所有带“+”号的数字的总和。

谁能解释一下这部分是什么意思？ dp[j]=dp[j]+dp[j-num]

代码如下：

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        w=(S+sum(nums))//2
        if (S+sum(nums))%2==1: return 0
        if sum(nums)<S: return 0
        dp=[0]*(w+1)
        dp[0]=1
        for num in nums:
            for j in range(w,num-1,-1):
                dp[j]=dp[j]+dp[j-num]
        return dp[-1]

这里是问题：

 You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. 
For each integer, you should choose one from + and - as its new symbol.
    
Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:

Input: nums is [1, 1, 1, 1, 1], S is 3. 
Output: 5
Explanation: 

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

There are 5 ways to assign symbols to make the sum of nums be target 3.

Answer 1

Sahadat 的回答是正确的，但对于 OP 来说可能不够全面。让我添加更多细节。数学等价问题是如何从列表中选择某些元素以求和为 w（符号不变）。然而，这个问题在 DP 中更容易处理。特别地，d[0]=1 因为我们有独特的方式达到 0（通过不选择任何元素）。之后，归纳地，对于我们处理的每个 num，我们知道达到 j 的解决方案的数量是 d[j]（意味着我们不选择 num）或 d[j-num]（意味着我们选择 num）。一旦我们遍历列表中的所有 nums，d[w] 将包含达到 w 的解决方案的数量。这也是原题的解法

Answer 2

我不想尝试从理论上解释为什么会这样，我只是想遍历逻辑并描述它。在您的示例中，nums = [1, 1, 1, 1, 1]

w=(S+sum(nums))//2       # in your example this is 4
dp=[0]*(w+1)             # your array is 5 elements long, its max index is w 
dp[0]=1                  # initialize first index to 1, everything else is 0 
        
for num in nums:                   # num will be 1 for 5 iterations
    for j in range(w,num-1,-1):    # j starts at the end and iterates backward. 
                                   # here j goes from index 4 to 0 every time
        dp[j]=dp[j]+dp[j-num].     # remember dp = [1, 0, 0, 0, 0]. but after 
                                      # the first completion of the inner loop, dp 
                                      # will be [1, 2, 0, 0, 0]. remember you have 
                                      # negative indices in this language. 
return dp[-1]          # so after all iterations... dp is [1, 2, 3, 4, 5]

您只是将初始的 1 - 即 dp = [1, 0, 0, 0, 0] - 推向数组的末尾。在每次迭代中，这种情况的发生方式取决于 num is 的大小。

为什么这行得通？让我们尝试一个不同的例子，看看对比。假设 nums = [7, 13] 并且 S 是 20。答案应该是 1，对吗？ 7 + 13 = 20，这就是可能的。

w=(S+sum(nums))//2       # now this is 20.
dp=[0]*(w+1)             # your array is 21 elements long, its max index is w 
dp[0]=1                  # initialize first index to 1, everything else is 0 
        
for num in nums:                   # so num will be 7, then 13, 2 iterations
    for j in range(w,num-1,-1):    # j starts at the end and iterates backward. 
                                   # on first iteration j goes from index 20 to 6
                                   # on 2nd iteration j goes from index 20 to 12 
        dp[j]=dp[j]+dp[j-num].     # so when num = 7, and you reach the 2nd last 
                                     # iteration of the inner loop... index 7 
                                     # you're gona set dp[7] to 1 via dp[7]+dp[0]
                                     # subsequently, when num = 13... when you're 
                                     # at dp[20] you'll do dp[20] = d[20]+d[7]. 
                                     # Thus now dp[20] = 1, which is the answer.
return dp[-1]

所以 num 越大...跳过越多，将 1 移到顶部的次数就越少。较大的 num 值分散了可以加起来达到给定 S 的可能组合。此算法说明了这一点。但请注意最后一个示例中 dp[0] 中的 1 向上移动到 dp[20] 的方式。正是因为7+13=20，唯一的组合。这些迭代和求和说明了所有这些可能的组合。

但是算法中如何考虑潜在的符号翻转？好吧，假设之前的S不是20，而是6。即13 - 7 = 6，唯一的解决方案。好吧...让我们看看这个例子：

w=(S+sum(nums))//2       # now this is 13. (20+6)/2 = 13.
dp=[0]*(w+1)             # your array is 14 elements long 
dp[0]=1                  # initialize first index to 1 again

for num in nums:             # so num will be 7, then 13, 2 iterations
    for j in range(w,num-1,-1):    
                           # j starts at the end and iterates backward. 
                           # on first iteration j goes from index 13 to 6
                           # on 2nd iteration j goes from index 13 to 12 
        dp[j]=dp[j]+dp[j-num]. 
                           # so this time, on the 2nd iteration, when 
                           # num = 13... you're at dp[13] 
                           # you'll do dp[13] = d[13]+d[0]. 
                           # Thus now dp[13] = 1, which is the answer.
                 # This time the 1 was moved directly from d0 to the end

return dp[-1]

所以这一次，当组合包含负数时，w 的大小为 13 导致解决方案：索引 d[13] + d[0] = 1。数组大小更小这样大的数直接加1

这很奇怪，我承认，你有 2 种不同的机制在工作，这取决于潜在的标志是什么。在正数和负数总和为 S 的情况下，较小的总数组长度导致 1 移动到最后一个槽。对于 2 个正数……这个中介将 1 向上移动了。但至少你能看出区别...

Leetcode第494题Target Sum动态规划部分难懂

Hard to understand the dynamic programming part of Leetcode question 494, Target Sum

python

dynamic-programming

python-3.x