代码随想录算法训练营第三十七天 | 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 协议》,转载必须注明作者和本文链接
《L03 构架 API 服务器》
你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程,JWT 概念及使用 和 API 开发相关的进阶知识。
《G01 Go 实战入门》
从零开始带你一步步开发一个 Go 博客项目,让你在最短的时间内学会使用 Go 进行编码。项目结构很大程度上参考了 Laravel。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

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