My Seventy-fifth Page - 组合总和Ⅳ - By Nicolas

这篇page是针对leetcode上的377.组合总和Ⅳ所写的。小尼先简单的说明一下这道题，就是给出一个由不同整数组成的数组nums，和一个目标整数target，需要从nums中造出并发返回总和为targey的元素的个数和。

小尼在这里做一个总结，在我们的完全背包问题里面分为排列和组合问题，没错就是我们高中所学的排列和组合问题，次题就是一个典型的排列问题，排列是讲究顺序的，也就是说，我们在排列的时候（1，2）和（2，1）是有区别的，小尼在这里也给出一个结论：

如果是求组合问题就是外层for循环遍历物品，内层是for循环遍历背包。

如果是求排列问题就是外层for循环遍历背包，内层for循环遍历物品。

小尼接下来讲一下这道题的动规五部曲：

1、确定dp数组以及下标的含义：dp[i]：凑成目标正整数为i的排列个数为dp[i]

2、确定递推公式：dp[i]可以由dp[i - nums[j]]推导出来，因为只要得到nums[i]，排列个数dp[i - nums[j]]，就是dp[i]的一部分。

3、dp数组如何初始化：其实就是dp[0] = 1就好了，因为我们的初始数不可以为0

4、确定递归顺序：因为这道题是一个组合问题，所以这道题的外层是遍历背包，内层是遍历物品

5、导出dp数组：只需要做一个导出工作即可

接下来小尼拉一下这道题解题的代码：

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp =  new int[target + 1];
        dp[0] = 1;
        for(int i = 0;i <= target; i++){
            for(int j = 0; j < nums.length; j++){
                if(i >= nums[j]){
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }
}

这道题其实没有特俗的地方，小尼其实希望跟大家分享的地方就是这里为什么就是会判断出组合而非排列，就是因为在这种条件下我们进行的遍历就是先判断将背包不断地放满的个数然后就是我们内层就是每一个物品都是可以取进去的，所以我们就会组成排列，我们可以看看小尼写的上一篇文章，那道题就是一个典型的组合问题，因为上一道题中我们的物品每一次取都是恒定的，也就是说我们只是考虑前面背包装满的情况，然后我们在多种的情况下进行装包，不论我们的情况是怎么样，我们装入的物品的大小一直都是恒定的，这样我们就不会出现后续还会出现之前出现过了的物品，这样就是达到我们组合的目的。

希望上面的讲解和代码段可以帮助到小伙伴们~~~