Day 50 | 动态规划 70. 爬楼梯 （进阶）、 322. 零钱兑换 、 279.完全平方数

70. 爬楼梯 （进阶）

题目
文章讲解

思路：排列问题，先遍历背包，再遍历物品

import java.util.*;

public class Main {
   
    public static void main(String[] args) {
   
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 输入台阶的总数
        int m = sc.nextInt(); // 每次最多可以爬的台阶数

        int[] dp = new int[n + 1]; // 创建一个数组来保存到达每一级台阶的方法数
        dp[0] = 1; // 初始条件：到达第0级台阶的方法数为1

        for (int i = 1; i <= n; i++) {
    // 从第1级台阶开始计算到达每一级台阶的方法数
            for (int j = 1; j <= m && j <= i; j++) {
    // 对于每一级台阶，尝试使用1到m步来爬
                dp[i] += dp[i - j]; // 将到达当前台阶的方法数加起来
            }
        }

        System.out.print(dp[n]); // 输出到达第n级台阶的方法数，即为所求的结果
    }
}

322. 零钱兑换

题目
文章讲解
视频讲解

思路：

1. dp[j]：凑足总额为j所需钱币的最少个数为dp[j]
2. 递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
3. 本题求钱币最小个数，钱币有顺序和没有顺序都可以，都不影响钱币的最小个数。所以本题并不强调集合是组合还是排列。

class Solution {
   
    public int coinChange(int[] coins, int amount) {
   
        int max = Integer.MAX_VALUE;
        int[] dp = new int[amount + 1]; // 创建一个数组来存储组成从0到'amount'的每个金额所需的最小硬币数量
        
        for (int j = 0; j < dp.length; j++) {
   
            dp[j] = max; // 将dp数组的所有元素初始化为最大值
        }
        dp[0] = 0; // 基本情况：组成金额0所需的硬币数量为0

        for (int i = 0; i < coins.length; i++) {
   
            for (int j = coins[i]; j <= amount; j++) {
   
                if (dp[j - coins[i]] != Integer.MAX_VALUE) // 检查是否可以使用面值为coins[i]的硬币来组成金额j
                    dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1); // 使用更小的硬币数量更新dp[j]
            }
        }

        return dp[amount] == max ? -1 : dp[amount]; // 返回组成该金额所需的最小硬币数量，如果不可能则返回-1
    }
}

279.完全平方数

题目
文章讲解
视频讲解

思路：

1. 注意初始化

class Solution {
   
    public int numSquares(int n) {
   
        int[] dp = new int[n + 1];

        int max = Integer.MAX_VALUE;

        for (int i = 0; i <= n; i++) {
   
            dp[i] = max;
        }
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
   
            for (int j = 1; j * j <= i; j++) {
   
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }

        return dp[n];

    }
}