界面做的比较好的网站,泉州专业建站品牌,wordpress源程序,设计购物网站咋做代码随想录第四十五天 Leetcode 70. 爬楼梯Leetcode 322. 零钱兑换Leetcode 279. 完全平方数 Leetcode 70. 爬楼梯
题目链接: 爬楼梯 自己的思路:之前是用斐波那契做的#xff0c;但是现在学了完全背包#xff0c;可以将m2拓展的更大一点#xff0c;我们可以将楼顶n设为背包… 代码随想录第四十五天 Leetcode 70. 爬楼梯Leetcode 322. 零钱兑换Leetcode 279. 完全平方数 Leetcode 70. 爬楼梯
题目链接: 爬楼梯 自己的思路:之前是用斐波那契做的但是现在学了完全背包可以将m2拓展的更大一点我们可以将楼顶n设为背包的容量将m设为物品的容量我们每次选物品而且物品可以重复问可以有多少种不同的选法而且这种是要考虑顺序的问题的所以和之前的组合总和其实是一个题目
正确思路:
代码:
class Solution {public int climbStairs(int n) {//物品的数量int m2;int[] dp new int[n1];dp[0] 1;for (int j0;jn;j){ //遍历背包for (int i1;im;i){ //遍历物品if (ji) dp[j]dp[j-i];}}return dp[n];}
}Leetcode 322. 零钱兑换
题目链接: 零钱兑换 自己的思路:想不到
正确思路:这个题可以看做是一个完全背包问题因为里面的钱是可以任意取重复个的动规五部曲1、dp数组的含义dp[j]表示的是当总金额为j时组成总金额的钱币的最小数量2、递推公式我们拿当第i个钱币来算如果我们不选这个钱币那么就是dp[j]情况那么如果选的话就是dp[j-coins[i]]1所以说取两者的最小值3、dp数组初始化dp[0]肯定是0主要是其他的我们要初始化为什么因为我们是求min值所以我们应该将他们都初始化为Integer的最大值4、遍历顺序由于这道题是求最小的数量所以先遍历背包和先遍历物品其实是一样的5、打印dp数组主要是用于debug
代码:
class Solution {public int coinChange(int[] coins, int amount) {int[] dp new int[amount1];for (int i 0;idp.length;i){dp[i] Integer.MAX_VALUE;}dp[0] 0;for (int i0;icoins.length;i){for (int jcoins[i];jamount;j) {//当dp[m]有效的时候才可以向后更新不然没有意义if (dp[j-coins[i]]!Integer.MAX_VALUE){dp[j] Math.min(dp[j],dp[j-coins[i]]1);}}}return (dp[amount]Integer.MAX_VALUE)?-1:dp[amount];}
}Leetcode 279. 完全平方数
题目链接: 完全平方数 自己的思路:和上一个题基本一样怪自己懒得思考
正确思路:只是改变了一下循环中的参数的定义其他基本都是不变的这个题一定可以由完全平方数组成所以我们初始化的时候非零的索引初始化为n因为dp[n]最大是n 代码:
class Solution {public int numSquares(int n) {int[] dp new int[n1];for (int i 0;idp.length;i){dp[i]n;}dp[0]0;for (int i 1;i*in;i){for (int ji*i;jn;j){if (dp[j-i*i]!n){dp[j]Math.min(dp[j],dp[j-i*i]1);}}}return dp[n];}
}
