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

518. 零钱兑换 II

解题方法

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

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

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. 组合总和 Ⅳ

解题方法

思路:与上一题零钱兑换思路一样,都是完全背包类型的题目,不同的点在于,上一题强调是组合,这一题强调的是排列。不要被组合这个词蒙蔽的双眼:joy:
代码随想录算法训练营第三十六天 | leetcode:零钱兑换 II,组合总和 Ⅳ

  1. dp数组的含义:dp[j]:当target为j时,在nums数组中可以组成不同的组合数为d[j]
  2. 确定递推公式:同样这里是求装满背包一共有多少种方式。
    所以递推公式:dp[j] += dp[j-nums[i]];
  3. 初始化dp数组:除了dp[0]=1,其余都初始化为0。
  4. 遍历顺序:与上一题不同,这一题求排列,需要先遍历背包,再遍历物品。如果先遍历物品则,递推公式$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];
    }
}

复杂度

时间复杂度

O(target * n),其中 n 为 nums 的长度

空间复杂度

O(target)

本作品采用《CC 协议》,转载必须注明作者和本文链接
《L04 微信小程序从零到发布》
从小程序个人账户申请开始,带你一步步进行开发一个微信小程序,直到提交微信控制台上线发布。
《G01 Go 实战入门》
从零开始带你一步步开发一个 Go 博客项目,让你在最短的时间内学会使用 Go 进行编码。项目结构很大程度上参考了 Laravel。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!