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

I found this solution which is extremely fast(beats 99.5%) and space-saving(beats 95%) at the same time. I understand most part, except the line: dp[j]=dp[j]+dp[j-num]

I understand the w is calculating the sum of all numbers with '+' sign.

Can anyone explain what this part means? dp[j]=dp[j]+dp[j-num]

Here is the code:

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]  

Here is the question:

 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.  

https://stackoverflow.com/questions/65820660/hard-to-understand-the-dynamic-programming-part-of-leetcode-question-494-target January 21, 2021 at 11:13AM