代码随想录算法训练营第四十五天|70. 爬楼梯 (进阶)、322. 零钱兑换 、279.完全平方数

2024-01-02 09:52:29

代码随想录算法训练营第四十五天|70. 爬楼梯 (进阶)、322. 零钱兑换 、279.完全平方数

爬楼梯 (进阶)

70. 爬楼梯 (进阶)
文章讲解:https://programmercarl.com/0070.%E7%88%AC%E6%A5%BC%E6%A2%AF%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85%E7%89%88%E6%9C%AC.html
题目链接:https://kamacoder.com/problempage.php?pid=1067
视频讲解:https://www.bilibili.com/video/BV1uK411o7c9/

自己看到题目的第一想法

完全背包,这道题求的不是组合数,而是排列数。因此用排列去做。

public class Test {
  public int climb(int m,int n){
      // 1. 确定dp数组定义:到台阶j的方法数和。
      int[] dp = new int[n + 1];
      dp[0] = 1;
      // 2. 确定递推公式,先遍历背包再遍历物品
      for(int j = 1; j <= n; j++){ // 背包
          for(int i = 1; i <=m ; i++){ // 物品
              dp[j] += dp[j - i];
          }
      }
      return dp[n]; 
  }
}

看完代码随想录之后的想法

题目就和上一天的377. 组合总和 Ⅳ题目一样,因为求的是排列,因此先遍历背包再遍历物品。

import java.util.Scanner;
class climbStairs{
    public static void main(String [] args){
        Scanner sc = new Scanner(System.in);
        int m, n;
        while (sc.hasNextInt()) {
            // 从键盘输入参数,中间用空格隔开
            n = sc.nextInt();
            m = sc.nextInt();

            // 求排列问题,先遍历背包再遍历物品
            int[] dp = new int[n + 1];
            dp[0] = 1;
            for (int j = 1; j <= n; j++) {
                for (int i = 1; i <= m; i++) {
                    if (j - i >= 0) dp[j] += dp[j - i];
                }
            }
            System.out.println(dp[n]);
        }
    }
}

自己实现过程中遇到哪些困难

还是没理解遍历顺序,等后面回头再看。不卡在这一章节。

零钱兑换

322. 零钱兑换
文章讲解:https://programmercarl.com/0322.%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2.html
题目链接:https://leetcode.cn/problems/coin-change/
视频讲解:https://www.bilibili.com/video/BV14K411R7yv/

自己看到题目的第一想法

看完代码随想录之后的想法

动态规划五步骤:

  1. 确定dp数组含义:dp[j]表示装满整数为j的背包,使用的最小硬币数量
  2. 确定递推公式:dp[j-coins[i]] + 1,表示j-coins[i]个背包下,只要再放一个coins[i]凑成dp[j]就是最小硬币数量了。
  3. 确定遍历顺序,先物品再背包

自己实现过程中遇到哪些困难

  1. 需要先将初始化dp数组为最大值
  2. 在递推公式处理中还需要判断 dp[j - coins[i]] != Integer.MAX_VALUE 才能处理值
 public int coinChange(int[] coins, int amount) {
     // 动态规划五步骤
     // 1. 确定dp数组含义:dp[j]表示装满整数为j的背包,使用的最小硬币数量
     // 2. 确定递推公式:dp[j-coins[i]] + 1,表示j-coins[i]个背包下,只要再放一个coins[i]凑成dp[j]就是最小硬币数量了。
     // 3. 确定遍历顺序,先物品再背包
     int max = Integer.MAX_VALUE;
     int[] dp = new int[amount + 1];
     //初始化dp数组为最大值
     for (int j = 0; j < dp.length; j++) {
         dp[j] = max;
     }
     //当金额为0时需要的硬币数目为0
     dp[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){
                 dp[j] = Math.min(dp[j],dp[j - coins[i]] + 1);
             }
         }
     }
     if(Objects.equals(dp[amount],Integer.MAX_VALUE)){
         return -1;
     }
     return dp[amount];

 }

完全平方数

  279.完全平方数
文章讲解:https://programmercarl.com/0279.%E5%AE%8C%E5%85%A8%E5%B9%B3%E6%96%B9%E6%95%B0.html
题目链接:https://leetcode.cn/problems/perfect-squares/
视频讲解:https://www.bilibili.com/video/BV12P411T7Br/

自己看到题目的第一想法

和零钱兑换差不多。物品是

看完代码随想录之后的想法

今日收获&学习时长

后面再回顾

文章来源:https://blog.csdn.net/shanshe7934/article/details/135190795
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。