嘉兴港区建设局网站,2018年网站开发,百度官网认证免费,电子商务网站的建设和维护70爬楼梯这道题之前已经做过#xff0c;是动态规划思想的入门#xff0c;想要爬上第n层阶梯#xff0c;看爬上n-1层的方法和n-2层的方法共有多少种#xff0c;两个相加就是爬上n层阶梯的方法。这里扩展到每次可以爬k层#xff0c;这样就是一个动态规划问题。因为每次可以爬…70爬楼梯这道题之前已经做过是动态规划思想的入门想要爬上第n层阶梯看爬上n-1层的方法和n-2层的方法共有多少种两个相加就是爬上n层阶梯的方法。这里扩展到每次可以爬k层这样就是一个动态规划问题。因为每次可以爬1-k层所以把k作为物品爬到n层作为背包容量爬的楼梯数k可以重复所以是个完全背包问题。定义数组dp[i]dp[i]表示爬上i层阶梯的方法数。初始化dp[0] 1因为爬上第0层的方法为1也就是不用动。因为爬楼梯的层数可以重复所以我理解成排列问题遍历顺序先背包容量再物品物品再内层循环每次就都可以从最小开始可以重复。 322零钱兑换目标数是背包容量零钱数组coins是物品dp[i]表示的是零钱的个数。初始化dp[0] 0因为0元的兑换不需要硬币所以是0.因为零钱是可以重复使用的所以是个完全背包问题但是零钱是个组合问题比如说6块钱可以用5元和1元零钱兑换也可以用1元和5元兑换和5元1元的顺序不同但是是同一种方法所以这是组合问题。组合问题要先遍历物品再遍历背包。 79完全平方数整数n时背包容量物品是完全平方数dp[i]表示和为n的最小物品数量。这里完全平方数可以重复使用并且是个组合问题和完全平方数的顺序无关所以是个多重背包的组合问题。需要先遍历物品再遍历背包容量。
70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢 示例 1
输入n 2
输出2
解释有两种方法可以爬到楼顶。
1. 1 阶 1 阶
2. 2 阶
示例 2
输入n 3
输出3
解释有三种方法可以爬到楼顶。
1. 1 阶 1 阶 1 阶
2. 1 阶 2 阶
3. 2 阶 1 阶提示
1 n 45
class Solution {public int climbStairs(int n) {// int [] dp new int[3];// if(n 3){// return n;// }// dp[0] 1;// dp[1] 2;// for(int i 2; i n; i){// dp[2] dp[1] dp[0];// dp[0] dp[1];// dp[1] dp[2];// }// return dp[2];int[] dp new int[n 1];int[] weigh {1, 2};dp[0] 1;for(int i 0; i n; i){for(int j 0; j weigh.length; j){if(i weigh[j]){dp[i] dp[i - weigh[j]];}}}return dp[n];}
}
322. 零钱兑换
给你一个整数数组 coins 表示不同面额的硬币以及一个整数 amount 表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额返回 -1 。
你可以认为每种硬币的数量是无限的。 示例 1
输入coins [1, 2, 5], amount 11
输出3
解释11 5 5 1
示例 2
输入coins [2], amount 3
输出-1
示例 3
输入coins [1], amount 0
输出0提示
1 coins.length 121 coins[i] 231 - 10 amount 104
class Solution {public int coinChange(int[] coins, int amount) {int len coins.length;int[] dp new int[amount 1];dp[0] 0;for(int i 1; i amount; i){dp[i] amount 1;}for(int i 0; i len; i){for(int j coins[i]; j amount; j){dp[j] Math.min(dp[j], dp[j - coins[i]] 1);}}if(dp[amount] amount){return -1;}return dp[amount];}
}
279. 完全平方数
给你一个整数 n 返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9 和 16 都是完全平方数而 3 和 11 不是。 示例 1
输入n 12
输出3
解释12 4 4 4
示例 2
输入n 13
输出2
解释13 4 9 提示
1 n 104
class Solution {public int numSquares(int n) {int[] dp new int[n 1];for(int i 0; i n; i){dp[i] n;}dp[0] 0;for(int i 1; i * i n ; i){for(int j i * i; j n; j){dp[j] Math.min(dp[j], dp[j - i * i] 1);}}return dp[n];}
}
