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

322. 零钱兑换

解题方法

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

dp数组的含义：dp[j]：凑足总额为j所需钱币的最少个数为dp[j]
确定递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

dp[j - coins[i]] + 1：表示放入coins[i]时，物品的数量。
dp[j]：表示没放入coins[i]时，物品的数量。

初始化dp数组：除了dp[0]=0,其余都初始化为PHP_INT_MAX。因为递推公式需要求得较小值。
遍历顺序：外层为物品（从小到大），内层为背包（从小到大）。

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物品数组。

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

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);
    }
}