Leetcode 377. 组合总和Ⅳ 入门dp C++实现

问题：Leetcode 377. 组合总和Ⅳ

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

算法1：

        和爬楼梯一样，定义 dfs ( i ) 表示爬 i 个台阶的方案数。考虑最后一步爬了 x = nums [ j ] 个台阶，那么问题变成爬 i − x 个台阶的方案数，即 dfs ( i − x ) 。所以有

注：如果 nums [ j ] > i 则跳过。

递归入口：dfs ( target ) ，也就是答案。

用记忆化搜索来优化：

        如果一个状态（递归入参）是第一次遇到，那么可以在返回前，把状态及其结果记到一个 memo 数组中。如果一个状态不是第一次遇到（memo 中保存的结果不等于 memo 的初始值），那么可以直接返回 memo 中保存的结果。
        注意：memo 数组的初始值一定不能等于要记忆化的值！例如初始值设置为 0，并且要记忆化的 dfs(i) 也等于 0，那就没法判断 0 到底表示第一次遇到这个状态，还是表示之前遇到过了，从而导致记忆化失效。一般把初始值设置为 −1。

代码：

class Solution {
    int dfs(int i,vector<int>&nums,vector<int>&memo){
        if(i == 0)  return 1;
        int& res = memo[i];
        if(res != -1)   return res;
        res = 0;
        for(int x : nums)
            if(x <= i)  res += dfs(i - x,nums,memo);
        return res;
    }
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> memo(target + 1,-1);
        return dfs(target,nums,memo);
    }
};

算法2:

我们可以去掉递归中的「递」，只保留「归」的部分，即自底向上计算。

        具体来说，dp [ i ] 的定义和 dfs ( i ) 的定义是一样的，都表示表示爬 i 个台阶的方案数。相应的递推式（状态转移方程）也和 dfs 一样：

注：如果 nums [ j ] > i 则跳过。答案为 dp [ target ] ，翻译自递归入口 dfs ( target ) 。

代码：

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