代码随想录算法训练营第三十七天 | leetcode:零钱兑换,完全平方数

322. 零钱兑换#

解题方法#

思路:与之前完全背包题型不同,这又算是一种新的题型,求解装满背包的最少物品数。之前的题型是,装满背包的最大价值,装满背包有多少种方式。

  1. dp 数组的含义:dp [j]:凑足总额为 j 所需钱币的最少个数为 dp [j]
  2. 确定递推公式:dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
    • dp [j - coins [i]] + 1:表示放入 coins [i] 时,物品的数量。
    • dp [j]:表示没放入 coins [i] 时,物品的数量。
  3. 初始化 dp 数组:除了 dp[0]=0, 其余都初始化为 PHP_INT_MAX。因为递推公式需要求得较小值。
  4. 遍历顺序:外层为物品(从小到大),内层为背包(从小到大)。

code#

class Solution {

    /**
     * @param Integer[] $coins
     * @param Integer $amount
     * @return Integer
     */
    function coinChange($coins, $amount) {
        $dp = [];
        $len = count($coins);
        //初始化dp数组为最大int值,方便后续求较小值
        for($i = 0; $i <= $amount; $i++){
            $dp[$i] = PHP_INT_MAX;
        }
        $dp[0] = 0;
        for($i = 0; $i < $len; $i++){
            for($j = $coins[$i]; $j <= $amount; $j++){
                // 如果dp[j - coins[i]]是PHP_INT_MAX则跳过,表示当前组合组成不了dp[j]
                if ($dp[$j - $coins[$i]] != PHP_INT_MAX) { 
                    $dp[$j] = min($dp[$j], $dp[$j-$coins[$i]] + 1);
                }
            }
        }
        //print_r($dp);
        if($dp[$amount] == PHP_INT_MAX) return -1;
        return $dp[$amount];
    }
}

复杂度#

时间复杂度

O (n * amount),其中 n 为 coins 的长度

空间复杂度

O(amount)

279. 完全平方数#

解题方法#

思路:与上题相同,都是求装满背包最小物品数,只是这道题没有给出物品数组,需要自己构造 nums 物品数组。

  1. dp 数组的含义:dp [j]:和为 j 的完全平方数的最少数量为 dp [j]
  2. 确定递推公式:dp[j] = min(dp[j], dp[j-nums[i] + 1]);
  3. 初始化 dp 数组:除了 dp[1]=1, 其余都初始化为 PHP_INT_MAX。
  4. 遍历顺序:外层为物品(从小到大),内层为背包(从小到大)。

code#

class Solution {

    /**
     * @param Integer $n
     * @return Integer
     */
    function numSquares($n) {
        //构建nums物品数组
        $nums = range(1, sqrt($n) + 1);
        foreach ($nums as $key => $val){
            $nums[$key] = $val * $val;
        }
        //print_r($nums);
        $dp = [];
        //初始化dp数组
        for ($i = 1; $i <= $n; $i++) {
            $dp[$i] = PHP_INT_MAX;
        }
        $dp[1] = 1;
        //遍历物品与背包
        for ($i = 1; $i < count($nums); $i++) {
            for ($j = $nums[$i]; $j <= $n; $j++) {
                $dp[$j] = min($dp[$j], $dp[$j - $nums[$i]] + 1);
            }
        }
        //print_r($dp);
        return $dp[$n];
    }
}

简化版#

class Solution {

    /**
     * @param Integer $n
     * @return Integer
     */
    function numSquares($n) {
        for ($i = 1; $i <= $n; $i++) $dp[$i] = PHP_INT_MAX;
        $dp[1] = 1;
        //遍历时使用i*i表示nums物品数组,节省空间
        for ($i = 1; $i * $i <= $n; $i++) {
            for ($j = $i * $i; $j <= $n; $j++) $dp[$j] = min($dp[$j], $dp[$j - $i * $i] + 1);
        }
        return $dp[$n];
    }
}

数学证明解法(时间复杂度最低)#

class Solution {

    /**
     * @param Integer $n
     * @return Integer
     */
     /**
        思路:这里运用到四平方和定理的推论
                若n=4^k*(8m+7),则个数为4,可以通过整除后 取余只 判断,
                若n本身等于一个数的平方,则无可厚非个数为1;
                若n等于一个数的平方加剩余数的平方,则个数为2;
                以上都不是则返回3. 
     */
    function numSquares($n) {
        if($this->isPerfectSquare($n)){
            return 1;
        }
        for($i=1;$i*$i<$n;$i++){
            if($this->isPerfectSquare($n-$i*$i)){
                return 2;
            }
        }
        if($this->checkAnswer4($n)){
            return 4;
        }
        return 3;
    }
    function checkAnswer4($n){
        while($n%4==0){
            $n/=4;
        }
        return $n%8==7;
    }
    function isPerfectSquare($n){
        $x=sqrt($n);
        return $x==intval($x);
    }
}

复杂度#

时间复杂度

O(n * √n)

空间复杂度

O(n)

本作品采用《CC 协议》,转载必须注明作者和本文链接
《L05 电商实战》
从零开发一个电商项目,功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
《G01 Go 实战入门》
从零开始带你一步步开发一个 Go 博客项目,让你在最短的时间内学会使用 Go 进行编码。项目结构很大程度上参考了 Laravel。