第377题---Combination Sum IV

• 题意描述

  • 给定一个都是正整数，没有重复的数组，给定一个目标数，求数组中组合成目标数的方式有几种，数组中的数可以多次使用

• 思路一

  • 类似于台阶的动态规划，res[0]代表，目标数为0的组合数；res[1]代表，目标数为1的组合数；依次类推，res[i]的组合数res[i] += res[i-num]

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