租个网站服务器多少钱,大连网站排名优化公司,顺德网络科技有限公司,微商城网站建设代理商动态规划part07 70. 爬楼梯 #xff08;进阶#xff09;解题思路总结 322. 零钱兑换解题思路总结 279.完全平方数解题思路 70. 爬楼梯 #xff08;进阶#xff09;
这道题目 爬楼梯之前我们做过#xff0c;这次再用完全背包的思路来分析一遍 文章讲解#xff1a; 70. 爬… 动态规划part07 70. 爬楼梯 进阶解题思路总结 322. 零钱兑换解题思路总结 279.完全平方数解题思路 70. 爬楼梯 进阶
这道题目 爬楼梯之前我们做过这次再用完全背包的思路来分析一遍 文章讲解 70. 爬楼梯 进阶
解题思路
我们之前做的 爬楼梯 是只能至多爬两个台阶。 这次改为一步一个台阶两个台阶三个台阶…直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢 这又有难度了这其实是一个完全背包问题。 1阶2阶.... m阶就是物品楼顶就是背包。 每一阶可以重复使用例如跳了1阶还可以继续跳1阶。 问跳到楼顶有几种方法其实就是问装满背包有几种方法。 此时大家应该发现这就是一个完全背包问题了 和题目动态规划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]);}}
}总结
本题看起来是一道简单题目稍稍进阶一下其实就是一个完全背包 如果我来面试的话我就会先给候选人出一个 本题原题看其表现如果顺利写出来进而在要求每次可以爬[1 - m]个台阶应该怎么写。 顺便再考察一下两个for循环的嵌套顺序为什么target放外面nums放里面。 这就能考察对背包问题本质的掌握程度候选人是不是刷题背公式一眼就看出来了。 这么一连套下来如果候选人都能答出来相信任何一位面试官都是非常满意的。 本题代码不长题目也很普通但稍稍一进阶就可以考察完全背包而且题目进阶的内容在leetcode上并没有原题一定程度上就可以排除掉刷题党了简直是面试题目的绝佳选择
322. 零钱兑换 如果求组合数就是外层for循环遍历物品内层for遍历背包。 如果求排列数就是外层for遍历背包内层for循环遍历物品。 这句话结合本题 大家要好好理解。 题目链接 322. 零钱兑换 视频讲解 322. 零钱兑换 文章讲解 322. 零钱兑换 解题思路
题目中说每种硬币的数量是无限的可以看出是典型的完全背包问题 动规五部曲分析如下
确定dp数组以及下标的含义 dp[j]凑足总额为j所需钱币的最少个数为dp[j]确定递推公式 递推公式dp[j] min(dp[j - coins[i]] 1, dp[j]);dp数组如何初始化 首先凑足总金额为0所需钱币的个数一定是0那么dp[0] 0; 考虑到递推公式的特性dp[j]必须初始化为一个最大的数否则就会在min(dp[j - coins[i]] 1, dp[j])比较的过程中被初始值覆盖。 所以下标非0的元素都是应该是最大值。确定遍历顺序 本题求钱币最小个数那么钱币有顺序和没有顺序都可以都不影响钱币的最小个数。 所以本题并不强调集合是组合还是排列。举例推导dp数组
总结
动态规划518.零钱兑换II 中求的是组合数动态规划377. 组合总和 Ⅳ 中求的是排列数。 而本题是要求最少硬币数量硬币是组合数还是排列数都无所谓所以两个for循环先后顺序怎样都可以
// 动态规划 完全背包
class Solution {public int coinChange(int[] coins, int amount) {int max Integer.MAX_VALUE;int[] dp new int[amount 1];//初始化dp数组为最大值for(int j 0; j dp.length; j){dp[j] max;}// 当金额为0时需要的硬币数目为0dp[0] 0;for(int i 0; i coins.length; i){//正序遍历完全背包每个硬币可以选择多次for(int j coins[i]; j amount; j){if(dp[j - coins[i]] ! max){// 选择硬币数目最小的情况dp[j] Math.min(dp[j], dp[j - coins[i]] 1);}}}return dp[amount] max ? -1 : dp[amount];}
}279.完全平方数 本题 和 322. 零钱兑换 基本是一样的大家先自己尝试做一做 题目链接 279.完全平方数 视频讲解 279.完全平方数 文章讲解 279.完全平方数 解题思路
和昨天的题目动态规划322. 零钱兑换 是一样一样的 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;}//如果不想要寫for-loop填充數組的話也可以用JAVA內建的Arrays.fill()函數。//Arrays.fill(dp, Integer.MAX_VALUE);//当和为0时组合的个数为0dp[0] 0;// 遍历物品for (int i 1; i * i n; i) {// 遍历背包for (int j i * i; j n; j) {//if (dp[j - i * i] ! max) {dp[j] Math.min(dp[j], dp[j - i * i] 1);//}//不需要這個if statement因爲在完全平方數這一題不會有湊不成的狀況發生 一定可以用1來組成任何一個n故comment掉這個if statement。}}return dp[n];}
}
