做oa系统的网站,怎么查询公司是不是中小企业,西安做网站找哪家公司好,微信网页开发教程Day38 力扣动态规划 :70.爬楼梯 #xff5c;322. 零钱兑换 #xff5c;279. 完全平方数 70. 爬楼梯 #xff08;进阶#xff09;第一印象看完题解的思路实现中的困难感悟代码 322. 零钱兑换第一印象dp数组递推公式初始化遍历顺序如果凑不出来返回 -1 看完题解的思路实现中… Day38 力扣动态规划 :70.爬楼梯 322. 零钱兑换 279. 完全平方数 70. 爬楼梯 进阶第一印象看完题解的思路实现中的困难感悟代码 322. 零钱兑换第一印象dp数组递推公式初始化遍历顺序如果凑不出来返回 -1 看完题解的思路实现中的困难感悟代码 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 第一印象
用完全背包的思路重新做一遍爬楼梯。
每次可能爬1或2个这个就是物品而且可以数量无限所以是完全背包。
物品的重量是1和2价值也是重量。
要爬n阶所以背包的大小是n。
也就是拿物品装满背包有多少种方法。
接下来要看排列还是组合呢
比如爬3阶先爬1再爬2 和 先爬2再爬1是两种所以是排列。
直接开做
看完题解的思路
就是用完全背包的思路去做一遍爬楼梯。
这里每次爬的台阶数量可以变成 1 2 3 …… m也就是有 m 个物品。
而本题只是 1 2 两个物品
实现中的困难
没有苦难
感悟
牛逼啊完全背包
代码
class Solution {public int climbStairs(int n) {//爬 i 阶楼梯有 dp[i] 种方法int[] dp new int[n 1];//初始化dp[0] 1;//先背包再物品排列for (int j 1; j dp.length; j) {for (int i 1; i 2; i) {if ( j i) {dp[j] dp[j - i];}}//打印dp数组for (int k 0; k dp.length; k) {System.out.print(dp[k] );}System.out.println();}return dp[n];}
}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 第一印象
我试试
dp数组
凑成 i 元需要的最少硬币数量是 dp[i]
递推公式
dp[j] min( dp[j], dp[j - coins[I] ] 1 )
初始化
画出二维数组体验一下过程
首先dp[0] 0是肯定的因为凑出0元就是0种方式题目的实例也告诉我们了。
其他元素呢按照习惯 还是dp[i] 0. 但这里不行了因为每次都取最小是如果初始化都是 0 的话每次取dp[j] 和dp[j-coins[i]] 1 小的那个那么dp数组永远都是 0 了。因为dp的含义是凑成 i 元最少需要dp[i] 个硬币。
所以dp数组要初始化为最大一开始我选择了MAX_VALUE但其实不合理后面再说。
遍历顺序
硬币数量和组合排列没关系我觉得for循环里外都行我选择了最习惯的组合 —— 先物品再背包
如果凑不出来返回 -1
怎么看凑不出来呢拿coins 只有2amount3 来举例子。
一开始数组都是MAX从 j2开始处理dp[2] mindp[2], dp[0] 1
所以dp[2]更新成了1
dp[3] min ( dp[3], dp[1] 1 )
dp[1] 和dp[3] 都是MAX那么dp[1] 1岂不是突破 MAX 了这就不合理了。
所以数组初始化应该是MAX - 1. 这样的话dp[1] 1 MAX, dp[3] MAX - 1. 选择更小的dp[3] 更新为MAX - 1.
既保证了不会溢出整形也保证了数组最大的是MAX - 1这样就算遇到下一个dp[3] 1的时候也不会溢出。
看完题解的思路
我照亮照亮题解是不是这么回事
确实在遍历顺序那里两个 for 循环内外都可以因为和顺序没关系。
我觉得可能是这样一个是逻辑上没关系另者递推公式是取最小而不是累加顺序就不会影响取最小这个计算过程。
因为1 1 2 和 2 1 1对于几种方法的dp数组来说排列的话是2种组合的话是1张
但如果dp数组记录的是最小硬币数量对于dp数组来说记录的都是 3.
同样dp数组如果记录的是最大价值对于dp数组来说记录的都是那个价值。
剩下的和我想的一样
他是用下面这样的方式避免了MAX溢出
//只有dp[j-coins[i]]不是初始最大值时该位才有选择的必要if (dp[j - coins[i]] ! max) {//选择硬币数目最小的情况dp[j] Math.min(dp[j], dp[j - coins[i]] 1);}实现中的困难
避免max溢出就行了
感悟
我真是天才
代码
class Solution {public int coinChange(int[] coins, int amount) {int[] dp new int[amount 1];//初始化dp[0] 0;for (int i 1; i dp.length; i) {dp[i] Integer.MAX_VALUE - 1;}for (int i 0; i coins.length; i) {for (int j coins[i]; j dp.length; j) {dp[j] Math.min(dp[j], dp[j - coins[i]] 1);}}if (dp[amount] Integer.MAX_VALUE - 1) return -1;return dp[amount];}
}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 第一印象
背包大小是 n
完全平方数是每个物品
我得先创建这个物品的数组才行。
但是多大呢
o ,体力给了背包最多10000大小那么完全平方数到10000就行也就是100个完全平方数
总之完全背包所以正序遍历和顺序没关系两个for循环里外都行。
我写写试试。
样例跑过了但是n比较大的时候就超过时间限制了比如n6665.
看完题解的思路
我看看怎么优化
哦原来不用生成那个物品数组这样会让for循环每次都做的很大。
诶我按题解的写法怎么也超时了。
我把打印数组的地方去掉了就通过了
尝试了一下按我自己的方法去掉打印数组也是不超时的。好奇怪啊。
实现中的困难
没啥苦难
感悟
无 不知道为什么如果吧打印dp数组的那个拿出来就会超时了。
代码
class Solution {public int numSquares(int n) {//dp数组int[] dp new int[n 1];//初始化Arrays.fill(dp, Integer.MAX_VALUE);dp[0] 0;//递推公式for (int i 1; i * i n; i) {for (int j i * i; j dp.length; j) {dp[j] Math.min(dp[j], dp[j - i * i] 1);}// //打印dp数组// for (int k 0; k dp.length; k) {// System.out.print(dp[k] );// }// System.out.println();}return dp[n];}
}
