代码随想录-算法训练营day45(动态规划07:爬楼梯进阶本,零钱兑换,完全平方数)

第九章 动态规划part07● 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  322. 零钱兑换  如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。这句话结合本题 大家要好好理解。
视频讲解：https://www.bilibili.com/video/BV14K411R7yv
https://programmercarl.com/0322.%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2.html  279.完全平方数  
本题 和 322. 零钱兑换 基本是一样的，大家先自己尝试做一做 
视频讲解：https://www.bilibili.com/video/BV12P411T7Br
https://programmercarl.com/0279.%E5%AE%8C%E5%85%A8%E5%B9%B3%E6%96%B9%E6%95%B0.html  往日任务
● day 1 任务以及具体安排：https://docs.qq.com/doc/DUG9UR2ZUc3BjRUdY  
● day 2 任务以及具体安排：https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG  
● day 3 任务以及具体安排：https://docs.qq.com/doc/DUGdqYWNYeGhlaVR6 
● day 4 任务以及具体安排：https://docs.qq.com/doc/DUFNjYUxYRHRVWklp 
● day 5 周日休息
● day 6 任务以及具体安排：https://docs.qq.com/doc/DUEtFSGdreWRuR2p4 
● day 7 任务以及具体安排：https://docs.qq.com/doc/DUElCb1NyTVpXa0Jj 
● day 8 任务以及具体安排：https://docs.qq.com/doc/DUGdsY2JFaFhDRVZH 
● day 9 任务以及具体安排：https://docs.qq.com/doc/DUHVXSnZNaXpVUHN4 
● day 10 任务以及具体安排：https://docs.qq.com/doc/DUElqeHh3cndDbW1Q 
●day 11 任务以及具体安排：https://docs.qq.com/doc/DUHh6UE5hUUZOZUd0 
●day 12 周日休息 
●day 13 任务以及具体安排：https://docs.qq.com/doc/DUHNpa3F4b2dMUWJ3 
●day 14 任务以及具体安排：https://docs.qq.com/doc/DUHRtdXZZSWFkeGdE 
●day 15 任务以及具体安排：https://docs.qq.com/doc/DUHN0ZVJuRmVYeWNv 
●day 16 任务以及具体安排：https://docs.qq.com/doc/DUHBQRm1aSWR4T2NK 
●day 17 任务以及具体安排：https://docs.qq.com/doc/DUFpXY3hBZkpabWFY 
●day 18 任务以及具体安排：https://docs.qq.com/doc/DUFFiVHl3YVlReVlr 
●day 19 周日休息
●day 20 任务以及具体安排：https://docs.qq.com/doc/DUGFRU2V6Z1F4alBH  
●day 21 任务以及具体安排：https://docs.qq.com/doc/DUHl2SGNvZmxqZm1X 
●day 22 任务以及具体安排：https://docs.qq.com/doc/DUHplVUp5YnN1bnBL  
●day 23 任务以及具体安排：https://docs.qq.com/doc/DUFBUQmxpQU1pa29C 
●day 24 任务以及具体安排：https://docs.qq.com/doc/DUEhsb0pUUm1WT2NP  
●day 25 任务以及具体安排：https://docs.qq.com/doc/DUExTYXVzU1BiU2Zl 
●day 26 休息 
●day 27 任务以及具体安排：https://docs.qq.com/doc/DUElpbnNUR3hIbXlY 
●day 28 任务以及具体安排：https://docs.qq.com/doc/DUG1yVHdlWEdNYlhZ  
●day 29 任务以及具体安排：https://docs.qq.com/doc/DUHZYbWhwSHRCRmp3 
●day 30 任务以及具体安排：https://docs.qq.com/doc/DUEdTVVhxbnJiY3BR 
●day 31 任务以及具体安排：https://docs.qq.com/doc/DUG1PQ1ZZY2xXY1ly 
●day 32 任务以及具体安排：https://docs.qq.com/doc/DUGFEdGFWeVhleFF1 
●day 33 周日休息 
●day 34 任务以及具体安排：https://docs.qq.com/doc/DUEh5WFVlQkp1U0p4  
●day 35 任务以及具体安排：https://docs.qq.com/doc/DUFRWc3BGRHFXZ1pO  
●day 36 任务以及具体安排：https://docs.qq.com/doc/DUERGbnhhRkFRVENZ 
●day 37 任务以及具体安排：https://docs.qq.com/doc/DUFVRd3p5SHFMSExQ  
●day 38 任务以及具体安排：https://docs.qq.com/doc/DUGNUdVpoT0VJR01l 
●day 39 任务以及具体安排：https://docs.qq.com/doc/DUE55cVJ5WkNoREhS 
●day 40 周日休息
●day 41 任务以及具体安排：https://docs.qq.com/doc/DUFhIUXRFYnVGUkFp 
●day 42 任务以及具体安排：42 第八章 动态规划 
●day 43 任务以及具体安排：43第八章 动态规划 
●day 44 任务以及具体安排：44 第八章 动态规划

day45

爬楼梯进阶版

完全背包问题

 import java.util.Scanner;class Main{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]);}}}

---

零钱兑换

 class Solution {public int coinChange(int[] coins, int amount) {//dp[j] = Math.min( dp[j - coins[i]] + 1, dp[j])//可以多次使用,背包从前向后遍历,多次添加coins[i]//求的是最小个数,跟是排列还是组合无关,所以遍历顺序可以颠倒int[] dp = new int[amount + 1];for(int j = 1; j <= amount ;j++){dp[j] = Integer.MAX_VALUE;//需要被递推公式覆盖,所以取最大值}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 - coins[i]] + 1, dp[j]);//也就是如果dp[j-coins[i]]这种情况不存在,根本凑不出来,就不做运算//因为公式里有dp[j - coins[i]] + 1,其实也是为了防止溢出}}return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];}}

---

完全平方数

 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;}//Arrays.fill(dp, Integer.MAX_VALUE);//当和为0时，组合的个数为0dp[0] = 0;// 遍历物品,物品从1到根号nfor (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];}}

---

感谢大佬分享:

代码随想录-算法训练营day45【动态规划07：爬楼梯(进阶)、零钱兑换、完全平方数】-CSDN博客