377.md

第一个自己的，第二个网友的，算是看出来差距了... 这题刷的这么丢脸，还是个public repo， 估计是要找不到工作了

水平大概差在这两句上 vector dp(target + 1); dp[0] = 1;

这题第一反应是递归手是有多生，还是看了提示的DP才想出来。 终于做出来个注意空特例的题了

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        if(nums.size() == 0)
            return 0;
        sort(nums.begin(), nums.end());
        int mark[1000000] = {};
        for(int i = 0; i < nums.size(); ++i){
            mark[nums[i]] = 1;
        }
        for(int i = nums[0]+1; i<= target; ++i){
            for(int j = 0; j < nums.size(); ++j){
                if(i-nums[j]>0 && mark[i-nums[j]])
                    mark[i] += mark[i-nums[j]];
            }
        }
        return mark[target];
    }
};

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        int n = (int)nums.size();
        if (n == 0) return 0;
        vector<int> dp(target + 1);
        dp[0] = 1;
        for (int i = 1; i <= target; i++)   {
            for (int v: nums) {
                if (i - v < 0) continue;
                dp[i] += dp[i - v];
            }
        }
        return dp[target];
    }
};