377. 组合总和 Ⅳ(leetcode)

https://leetcode.cn/problems/combination-sum-iv/description/

此篇题解解释了为什么不能直接用二维完全背包的方式做
不过还是建议把这个题当成一个爬楼梯来做

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        // f[i]表示若干数中选择,所能得到的值为i的个数(爬楼梯)
        // 以第i个数选择多少来划分子集
        // f[i] = f[i-nums[0]] + f[i-nums[1]] + f[i-nums[2]] + ... + f[i-nums[size-1]] 
        // f[0] = 1
        // 答案是f[target]
        unsigned int f[target+10];
        memset(f,0,sizeof f);
        f[0]=1; // 不选物品,能拿0的选法种数
        for(int j=0;j<=target;j++)
        {
            for(int i=0;i<nums.size();i++)
                if(j>=nums[i])
                    f[j]+=f[j-nums[i]];
        }
        return f[target];
    }
};