求解释一段代码

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int s) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        return sum < s || (s + sum) & 1 ? 0 : subsetSum(nums, (s + sum) >> 1); 
    }   

    int subsetSum(vector<int>& nums, int s) {
        int dp[s + 1] = { 0 };
        dp[0] = 1;
        for (int n : nums)
            for (int i = s; i >= n; i--)
                dp[i] += dp[i - n];
        return dp[s];
    }
};

这段里面的:

for (int n : nums)
            for (int i = s; i >= n; i--)
                dp[i] += dp[i - n];

是在做什么呢?
为什么这样正确?
谢谢!

这个是经典的dp,knapsack问题,就是从拿掉n的话的位置来deduce

你可以参考 climbing stairs https://leetcode.com/problems/climbing-stairs/description/ 这些基本的题目,思路一样

1 Like