代码随想录-算法训练营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时，组合的个数为0
dp[0] = 0;
// 遍历物品,物品从1到根号n
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];
}
}
感谢大佬分享:
代码随想录-算法训练营day45【动态规划07：爬楼梯(进阶)、零钱兑换、完全平方数】-CSDN博客
原文地址：https://blog.csdn.net/weixin_61931006/article/details/144328189
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！