刷题日记39 | 70. 爬楼梯、322. 零钱兑换、279.完全平方数
最新回答
空城已无她
2022-08-06 23:42:58
这三道题目（70.爬楼梯、322.零钱兑换、279.完全平方数）都可以用动态规划中的完全背包思路来解决，但具体实现细节有所不同。以下是对每道题目的详细解析和代码实现：
70. 爬楼梯问题描述：假设你正在爬楼梯，每次你可以爬1个或2个台阶。问到达第n个台阶有多少种不同的方法。
完全背包思路：可以将这个问题看作是一个求排列的背包问题，即每次可以选择爬1个或2个台阶，求到达第n个台阶的所有可能排列数。
代码实现：
class Solution { public int climbStairs(int n) { int[] dp = new int[n + 1]; dp[0] = 1; // 初始条升陪件，到达第0个台阶有1种方法（即不爬） for (int j = 0; j <= n; j++) { // 遍历背包（即台阶数） for (int i = 1; i <= 2; i++) { // 遍历物品（即每次爬的台阶数） if (j >= i) { dp[j] += dp[j - i]; // 累加到达当前台阶的方法数 } } } return dp[n]; }}322. 零钱兑换问题描述：给定不同面额的硬币和一个总金陵笑厅额，计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回-1。
完全背包思路：这个问尺隐题与排列组合无关，单纯是求出相加为总金额的最小硬币个数。因此，物品和背包的遍历顺序可以互换。
代码实现：
import java.util.Arrays;class Solution { public int coinChange(int[] coins, int amount) { int[] dp = new int[amount + 1]; Arrays.fill(dp, Integer.MAX_VALUE); // 初始化为最大值，以便后续取最小值 dp[0] = 0; // 初始条件，凑成金额0所需硬币数为0 for (int coin : coins) { // 遍历物品（即硬币面额） for (int j = coin; j <= amount; j++) { // 遍历背包（即金额） if (dp[j - coin] != Integer.MAX_VALUE) { // 如果前一个金额可以凑成 dp[j] = Math.min(dp[j], dp[j - coin] + 1); // 更新当前金额的最小硬币数 } } } return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount]; // 返回结果 }}279. 完全平方数问题描述：给定正整数n，找到若干个完全平方数（比如1, 4, 9, 16, ...）使得它们的和等于n。需要让组成和的完全平方数的个数最少。
完全背包思路：这个问题同样与排列组合无关，可以看作是一个完全背包问题，即每次可以选择一个完全平方数，求组成给定数的最小完全平方数个数。
代码实现：
import java.util.Arrays;class Solution { public int numSquares(int n) { int[] dp = new int[n + 1]; Arrays.fill(dp, Integer.MAX_VALUE); // 初始化为最大值 dp[0] = 0; // 初始条件，组成0需要0个完全平方数 for (int i = 1; i * i <= n; i++) { // 遍历物品（即完全平方数） int square = i * i; for (int j = square; j <= n; j++) { // 遍历背包（即目标数） if (dp[j - square] != Integer.MAX_VALUE) { // 如果前一个数可以组成 dp[j] = Math.min(dp[j], dp[j - square] + 1); // 更新当前数的最小完全平方数个数 } } } return dp[n]; // 返回结果 }}总结- 70.爬楼梯：可以看作是一个求排列的背包问题，需要先遍历背包再遍历物品。
- 322.零钱兑换：与排列组合无关，单纯求最小硬币个数，物品和背包的遍历顺序可以互换。初始化时需将所有值设为Integer.MAX_VALUE，以便后续取最小值。
- 279.完全平方数：同样与排列组合无关，可以看作是一个完全背包问题。初始化时也需将所有值设为Integer.MAX_VALUE。
通过这三道题目的练习，可以加深对动态规划中完全背包问题的理解，并掌握不同遍历顺序对结果的影响。
热门标签
