377. Combination Sum IV

本题发现用dfs是要超时的，看了别人的答案发现是要dp。

• dp[i] 表示target = i 时的组合种数。所以， ans = dp[target].
• dp[i] = sum { dp[i - nums[0]], dp[i - nums[1]], ... , dp[i - nums[sizeOfNums-1]] }
• dp[0] = 1 (理解这个非常重要， 从下面的推导就可以知道为啥dp[0] = 1)

对于nums = {1,2}, target = 3.

• dp[3] = dp[3-1] + dp[3-2] = dp[2] + dp[1]
• dp[2] = dp[2-1] + dp[2-2] = d[1] + dp[0], 之所以这里有个dp[0]是因为nums里有一个大小和2 相等的数，所以相减为0，所以算是一个组合，所以为dp[0] =1.
• dp[1] = dp[0]+dp[-1]，明显负数是不可能达到的，所以dp[负数] = 0。

#include<vector>
#include<algorithm>
#include<cstdio>
#include <unordered_map>
#include <cmath>
using namespace std;

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        
        // ans = dp[target]
        vector<int> dp(target + 1);
        
        sort(nums.begin(), nums.end());
        
        int sizeOfNums = (int)nums.size();
        
        //
        dp[0] = 1;
        
        for (int i = 1; i <= target; i++)
        {
            dp[i] = 0;
            for (int j = 0; j < sizeOfNums; j++)
            {
                if (i- nums[j] >= 0)
                {
                    dp[i] += dp[i - nums[j]];
                }
                else
                {
                    // if i- nums[j] < 0
                    break;
                }
            }
        }

        return dp[target];
    }
};