【随想录】Day45—第九章 动态规划part07

本文主要是介绍【随想录】Day45—第九章 动态规划part07，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

题目1: 70. 爬楼梯（进阶版）

• 题目链接：卡码网：57. 爬楼梯

---

1- 思路

动规五部曲

• 1. 确定 dp 数组含义
  • dp[i]：爬到有i个台阶的楼顶，有dp[i]种方法。
• 2. 确定递推公式
  • dp[j] += dp[j-i]
• 3. dp 数组初始化
  • 既然递归公式是 dp[i] += dp[i - j]，那么dp[0] 一定为1，dp[0]是递归中一切数值的基础所在，如果dp[0]是0的话，其他数值都是0了。
• 4. 遍历顺序（所求为组合，因此需要先遍历背包再遍历物品）
  • 这是背包里求排列问题，即：1、2 步 和 2、1 步都是上三个台阶，但是这两种方法不一样！
  • 所以需将target放在外循环，将nums放在内循环。
  • 每一步可以走多次，这是完全背包，内循环需要从前向后遍历。

---

2- 题解

⭐爬楼梯——题解思路

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while(sc.hasNext()){int n = sc.nextInt();  // 楼梯数    ——> 背包int m = sc.nextInt();  // 可以爬的台阶 ——> 商品// 1. 定义dp数组// 爬到 j 阶的种类数int[] dp = new int[n+1];// 2. 递推公式// dp[j] += dp[j-weight[i]]// 3. 初始化dp[0] = 1;// 4. 遍历顺序// 所求的是种类 所以 1 2 方式和 2 1 是不一样的// 先遍历背包 后 遍历 物品// 背包：从 小到大 j 从 1 到 n// 物品：从 小到大 i 从 1 到 mfor(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]);}}
}

---

题目2: 零钱兑换

• 题目链接：322. 零钱兑换

---

1- 思路

动规五部曲

• 1. 确定 dp 数组含义
  • dp[j]：凑足总额为j所需钱币的最少个数为dp[j]
• 2. 确定递推公式
  • 凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]，那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j]（考虑coins[i]）
  • 所以dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。
  • 递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
• 3. dp 数组初始化
  • 先初始化所有数组值为 Integer.MAX_VALUE
  • 首先凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0;
• 4. 遍历顺序（所求为组合，因此需要先遍历背包再遍历物品）
  • 所以本题并不强调集合是组合还是排列。
  • 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
  • 如果求排列数就是外层for遍历背包，内层for循环遍历物品。
  • 所以本题的两个for循环的关系是：外层for循环遍历物品，内层for遍历背包或者外层for遍历背包，内层for循环遍历物品都是可以的！

---

2- 题解

⭐零钱兑换——题解思路

class Solution {public int coinChange(int[] coins, int amount) {// 背包：amount// 物品：coins// 求：最少硬币数// 确定 dp 数组含义int[] dp = new int[amount+1];// 2. 确定递推公式// dp[j] = Math.min(dp[j],dp[j-weight[i]]+value[i]);// 3. 初始化int max = Integer.MAX_VALUE;for (int j = 0; j < dp.length; j++) {dp[j] = max;}dp[0] = 0;// 4. 确定遍历顺序// 先遍历 背包 后遍历 商品for(int i = 0 ; i < coins.length;i++ ){for(int j = coins[i] ; j <= amount ;j++){//只有dp[j-coins[i]]不是初始最大值时，该位才有选择的必要if (dp[j - coins[i]] != max){dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);}}}return dp[amount] == max ? -1 : dp[amount];}
}

---

题目3:完全平方数

• 题目链接：279. 完全平方数

---

1- 思路

动规五部曲

• 1. 确定 dp 数组含义
  • dp[j]：和为j的完全平方数的最少数量为dp[j]
• 2. 确定递推公式
  • dp[j] 可以由 dp[j - i * i]推出， dp[j - i * i] + 1 便可以凑成dp[j]。
  • 此时我们要选择最小的 dp[j] ，所以递推公式：dp[j] = min(dp[j - i * i] + 1, dp[j])
• 3. dp 数组初始化
  • dp数组初始化为 max
  • dp[0] = 0
• 4. 遍历顺序（所求为组合，因此需要先遍历背包再遍历物品）
  • 先遍历物品 再 遍历背包

---

2- 题解

⭐完全平方数——题解思路

class Solution {public int numSquares(int n) {// 1. 定义 dp 数组// 组成数字 i 的最小 完全平方数的个数int[] dp = new int[n+1];int max = Integer.MAX_VALUE;for (int j = 0; j <= n; j++) {dp[j] = max;}// 2. 递推公式// dp[j] = Math.min(dp[j],dp[j-weight[i]]+1);// 3. 初始化dp[0] = 0;// 4. 遍历顺序// 先遍历商品// 再遍历背包for(int i = 1 ; i*i <= n;i++){for(int j = i*i ; j <= n;j++ ){dp[j] = Math.min(dp[j-i*i]+1,dp[j]);}}return dp[n];}
}

---

这篇关于【随想录】Day45—第九章 动态规划part07的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---