代码随想录算法训练营第三十六天 | leetcode：零钱兑换 II,组合总和 Ⅳ

518. 零钱兑换 II

解题方法

思路：本题物品就是硬币coins,与之前背包问题不一样的是，背包物品可以无限使用，还记得之前01背包一维数组那里强调过，内层循环背包时候：需要倒叙循环，就是为了避免同一个物品重复使用。这不就巧了，这里刚好可以重复使用。而这样的背包问题被称为完全背包问题。

dp数组的含义：dp[j]：凑成总金额j的货币组合数为dp[j]
确定递推公式：与目标和一样，这里是求装满背包一共有多少种方式，而不是求最大价值。
所以递推公式与目标和一样：dp[j] += dp[j-coins[i]];
初始化dp数组：除了dp[0]=1,其余都初始化为0。
遍历顺序：外层为物品（从小到大），内层为背包（从小到大）。
注意题目描述中是凑成总金额的硬币组合数，组合不强调元素之间的顺序，排列强调元素之间的顺序。

code

class Solution {
    /**
     * @param Integer $amount
     * @param Integer[] $coins
     * @return Integer
     */
    function change($amount, $coins) {
        //dp[j] = 总金额为j时，有dp[j]种方法可以凑成j
        //dp[j] += dp[j-coin[i]];
        $dp[0] = 1;
        for($i = 0; $i < count($coins); $i++){
            for($j = $coins[$i]; $j <= $amount; $j++){
                $dp[$j] += $dp[$j-$coins[$i]];
            }
        }
        return $dp[$amount];
    }
}

复杂度

时间复杂度

O(mn)，其中 m 是amount，n 是 coins 的长度

空间复杂度

O(m)

377. 组合总和 Ⅳ

解题方法

思路：与上一题零钱兑换思路一样，都是完全背包类型的题目，不同的点在于，上一题强调是组合，这一题强调的是排列。不要被组合这个词蒙蔽的双眼

dp数组的含义：dp[j]：当target为j时，在nums数组中可以组成不同的组合数为d[j]
确定递推公式：同样这里是求装满背包一共有多少种方式。
所以递推公式：dp[j] += dp[j-nums[i]];
初始化dp数组：除了dp[0]=1,其余都初始化为0。
遍历顺序：与上一题不同，这一题求排列，需要先遍历背包，再遍历物品。如果先遍历物品则，递推公式$j-$nums[$i]会有负数情况，导致排列数缺失的情况。

code

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function combinationSum4($nums, $target) {
        for($j = 0; $j <= $target; $j++){
            //$dp[$j] = 0;
            $dp1[$j] = 0;
        }
        //$dp[0] = 1;
        $dp1[0] = 1;
        // for($i = 0; $i < count($nums); $i++){
        //     for($j = 0; $j <= $target; $j++){
        //         //如果先遍历物品则，递推公式$j-$nums[$i]会有负数情况，导致累计数会少
        //         if ($j >= $nums[$i]){
        //             $dp[$j] += $dp[$j-$nums[$i]];
        //         }
        //     }
        // }
        // print_r($dp);
        for($j = 1; $j <= $target; $j++){
            for($i = 0; $i < count($nums); $i++){
                if ($j >= $nums[$i]){
                    $dp1[$j] += $dp1[$j-$nums[$i]];
                }
            }
        }
        //print_r($dp1);
        return $dp1[$target];
    }
}