算法训练营Day39

#Java #动态规划

Feeling and experiences：

爬楼梯（进阶版）：卡码网题目链接

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。?

每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？?

注意：给定 n 是一个正整数。

和最初版本的爬楼梯来对比：本题能爬的阶数不再是 1 或 2 ，而是m；

代码如下：

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();
        
        //创建dp数组 ，含义：到i级台阶，需要dp[i]种方法
        int[] dp = new int[n+1];
       
       //初始化dp数组
       dp[0] = 1;
       
       //循环 ，递推
       for(int i = 1;i<=n;i++){ //外层循环：背包
           for(int j = 1;j<= m;j++){ //内层循环：物品
               if(i >= j){
                   dp[i]+=dp[i-j];
               }
           }
       }
       
        System.out.print(dp[n]);
    }    
}

这里递推模拟一下：（假如 n = 4，m = 2）

1. 当?i?=?1（只有1级台阶）：
? 可以从第0级走1级到达第1级，所以?dp[1]?=?dp[0]?=?1。

2. 当?i?=?2（有2级台阶）：
? 可以从第0级走2级到达第2级，或者从第1级走1级到达。所以?dp[2]?=?dp[0]?+?dp[1]?=?1?+?1?=?2。

3. 当?i?=?3（有3级台阶）：
? 可以从第1级走2级到达第3级，或者从第2级走1级到达。所以?dp[3]?=?dp[1]?+?dp[2]?=?1?+?2?=?3。

4. 当?i?=?4（有4级台阶）：
? 可以从第2级走2级到达第4级，或者从第3级走1级到达。所以?dp[4]?=?dp[2]?+?dp[3]?=?2?+?3?=?5。

最终结果，dp[4]?=?5，表示到达第4级台阶共有5种方法。

通过这道题，对内外循环再做一个详细的解释：（加深理解）

1. 外层循环?(for(int?i?=?1;?i?<=?n;?i++)):
? 这个循环遍历每一级台阶，从第1级到第?n?级。
? 在每次迭代中，i?表示当前目标台阶。我们要计算到达这一级台阶的所有可能的方法数。
? 外层循环确保了我们逐步建立到达每一级台阶的方法数，这是动态规划的核心特性——使用已解决的子问题来帮助解决更大的问题。

2. 内层循环?(for(int?j?=?1;?j?<=?m;?j++)):
? 对于每一级台阶?i，这个循环考虑所有可能的跳跃步数来到达这一级台阶。
? j?表示从前一个台阶跳跃的步数，它可以从1变化到?m（最大步数）。
? 在每次迭代中，如果?i?大于或等于?j，这意味着可以从?i-j?级台阶跳跃?j?步到达?i?级台阶。我们通过累加?dp[i-j]（到达第?i-j?级台阶的方法数）来更新?dp[i]。

零钱兑换：力扣题目链接

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回?-1 。

你可以认为每种硬币的数量是无限的。

示例?1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

每种硬币数量是无限的！！！

class Solution {
    public int coinChange(int[] coins, int amount) {
    
    //创建dp数组 ，含义：凑到amount有dp[amount]
    int []dp = new int[amount+1];
    Arrays.fill(dp,amount+1);

    //初始化dp数组
    dp[0] = 0;
    //循环，递推
    for(int i =1;i<=amount;i++){
        for(int j =0;j< coins.length;j++){
            if(coins[j] <= i){
                dp[i] = Math.min(dp[i],dp[i-coins[j]] + 1);
            }
        }
    }
    return dp[amount] > amount? -1: dp[amount];
    }
}

为什么会用Arrays.fill 来把dp数组的元素 设置为 amount+1 ；

因为amount + 1，是一个“不可达值”，用于后序的 Math.min()函数 来进行结果的更新。

?外层循环?(for(int?i?=?1;?i?<=?amount;?i++)):
? 遍历所有从?1?到?amount?的金额。
? 每次迭代计算组成金额?i?所需的最少硬币数。

?内层循环?(for(int?j?=?0;?j?<?coins.length;?j++)):
? 遍历每一种硬币的面值。
? 如果当前硬币的面值?coins[j]?小于等于当前金额?i，则考虑使用这枚硬币。
? 使用?Math.min(dp[i],?dp[i-coins[j]]?+?1)?来更新?dp[i]。这里的?dp[i-coins[j]]?+?1?表示如果使用这枚硬币，组成金额?i?所需的硬币数量（当前金额减去硬币面值的最少硬币数?+?这枚硬币）。

完全平方数：力扣题目链接

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例?1：

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

其本质还是背包问题 ，就是把可取的元素变成了平方数，在可取元素上做了改变！

这道题基本和上一个题：零钱兑换 是一样的，按照其模板来写：(先物品再背包）

class Solution {
    public int numSquares(int n) {
    //按照 零钱兑换的模板来写
    //创建dp数组
    int []dp = new int[n+1];
    //同理，还是要用到Arrays.fill 来赋值
    Arrays.fill(dp,n+1);

    //初始化
    dp[0] = 0;
    
    //循环递推 ：先物品再背包
    for(int i =1;i<=n;i++){
        for(int j =i*i;j<=n;j++){
            dp[j] = Math.min(dp[j],dp[j-i*i]+1);
        }
    }
return dp[n];
    }
}

?先背包再物品：（不用Arrays.fill 赋值）

class Solution {
    // 版本二， 先遍历背包, 再遍历物品
    public int numSquares(int n) {
        int max = Integer.MAX_VALUE;
        int[] dp = new int[n + 1];
        // 初始化
        for (int j = 0; j <= n; j++) {
            dp[j] = max;
        }
        // 当和为0时，组合的个数为0
        dp[0] = 0;
        // 遍历背包
        for (int j = 1; j <= n; j++) {
            // 遍历物品
            for (int i = 1; i * i <= j; i++) {
                dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
            }
        }
        return dp[n];
    }
}

“移舟靠岸
案前惟剩空盏
莫怨良辰短
曲终了韵意未完”?

Fighting！