网站建设与策划,搜索引擎营销的五大特点,苏州营销型网站建设方法,网站模糊背景文章目录 Day45爬楼梯题目思路代码 零钱兑换题目思路代码 完全平方数题目思路代码 Day45
爬楼梯
70. 爬楼梯 - 力扣#xff08;LeetCode#xff09;
题目
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢… 文章目录 Day45爬楼梯题目思路代码 零钱兑换题目思路代码 完全平方数题目思路代码 Day45
爬楼梯
70. 爬楼梯 - 力扣LeetCode
题目
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
注意给定 n 是一个正整数。
示例 1 输入 2 输出 2 解释 有两种方法可以爬到楼顶。
1 阶 1 阶2 阶
示例 2 输入 3 输出 3 解释 有三种方法可以爬到楼顶。
1 阶 1 阶 1 阶1 阶 2 阶2 阶 1 阶
思路
动规五部曲分析如下
确定dp数组以及下标的含义
dp[i]爬到有i个台阶的楼顶有dp[i]种方法。
确定递推公式
在动态规划494.目标和 (opens new window)、 动态规划518.零钱兑换II (opens new window)、动态规划377. 组合总和 Ⅳ (opens new window)中我们都讲过了求装满背包有几种方法递推公式一般都是dp[i] dp[i - nums[j]];
本题呢dp[i]有几种来源dp[i - 1]dp[i - 2]dp[i - 3] 等等即dp[i - j]
那么递推公式为dp[i] dp[i - j]
dp数组如何初始化
既然递归公式是 dp[i] dp[i - j]那么dp[0] 一定为1dp[0]是递归中一切数值的基础所在如果dp[0]是0的话其他数值都是0了。
下标非0的dp[i]初始化为0因为dp[i]是靠dp[i-j]累计上来的dp[i]本身为0这样才不会影响结果
确定遍历顺序
这是背包里求排列问题即1、2 步 和 2、1 步都是上三个台阶但是这两种方法不一样
所以需将target放在外循环将nums放在内循环。
每一步可以走多次这是完全背包内循环需要从前向后遍历。
举例来推导dp数组
介于本题和动态规划377. 组合总和 Ⅳ (opens new window)几乎是一样的这里我就不再重复举例了。
代码
class Solution {public int climbStairs(int n) {int dp[] new int[n 1];int step[] new int[]{1,2};dp[0] 1;for(int i 0; i n 1; i){for(int j 0; j step.length; j){if(i step[j]){dp[i] dp[i - step[j]];}}}return dp[n];}
}零钱兑换
322. 零钱兑换 - 力扣LeetCode
题目
给定不同面额的硬币 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
示例 4
输入coins [1], amount 1输出1
示例 5
输入coins [1], amount 2输出2
提示
1 coins.length 121 coins[i] 2^31 - 10 amount 10^4
思路
确定dp数组以及下标的含义
dp[j]: 凑出 j 元最少需要 dp[j] 枚硬币
确定递推公式
凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]那么只需要加上一个钱币coins[i]即dp[j - coins[i]] 1就是dp[j]考虑coins[i]
所以dp[j] 要取所有 dp[j - coins[i]] 1 中最小的。
递推公式dp[j] min(dp[j - coins[i]] 1, dp[j]);
dp数组如何初始化
首先凑足总金额为0所需钱币的个数一定是0那么dp[0] 0;
其他下标对应的数值呢
考虑到递推公式的特性dp[j]必须初始化为一个最大的数否则就会在min(dp[j - coins[i]] 1, dp[j])比较的过程中被初始值覆盖。
所以下标非0的元素都是应该是最大值。
确定遍历顺序
本题求钱币最小个数那么钱币有顺序和没有顺序都可以都不影响钱币的最小个数。
所以本题并不强调集合是组合还是排列。
如果求组合数就是外层for循环遍历物品内层for遍历背包。
如果求排列数就是外层for遍历背包内层for循环遍历物品。
在动态规划专题我们讲过了求组合数是动态规划518.零钱兑换II (opens new window)求排列数是动态规划377. 组合总和 Ⅳ (opens new window)。
所以本题的两个for循环的关系是外层for循环遍历物品内层for遍历背包或者外层for遍历背包内层for循环遍历物品都是可以的
那么我采用coins放在外循环target在内循环的方式。
本题钱币数量可以无限使用那么是完全背包。所以遍历的内循环是正序
举例推导dp数组
以输入coins [1, 2, 5], amount 5为例
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nOwSZb9p-1690615913100)(https://code-thinking-1253855093.file.myqcloud.com/pics/20210201111833906.jpg “322.零钱兑换”)]
代码
class Solution {public int coinChange(int[] coins, int amount) {int dp[] new int[amount 1];Arrays.fill(dp, Integer.MAX_VALUE);dp[0] 0;for(int i 0; i amount 1; i){for(int j 0; j coins.length; j){if(i coins[j] dp[i - coins[j]] ! Integer.MAX_VALUE){dp[i] Math.min(dp[i], dp[i - coins[j]] 1);}}}return dp[amount] Integer.MAX_VALUE ? -1 : dp[amount];}
}完全平方数
279. 完全平方数 - 力扣LeetCode
题目
给定正整数 n找到若干个完全平方数比如 1, 4, 9, 16, …使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
给你一个整数 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 10^4
思路
可能刚看这种题感觉没啥思路又平方和的又最小数的。
我来把题目翻译一下完全平方数就是物品可以无限件使用凑个正整数n就是背包问凑满这个背包最少有多少物品
感受出来了没这么浓厚的完全背包氛围
确定dp数组dp table以及下标的含义
dp[j]和为j的完全平方数的最少数量为dp[j]
确定递推公式
dp[j] 可以由dp[j - i * i]推出 dp[j - i * i] 1 便可以凑成dp[j]。
此时我们要选择最小的dp[j]所以递推公式dp[j] min(dp[j - i * i] 1, dp[j]);
dp数组如何初始化
dp[0]表示 和为0的完全平方数的最小数量那么dp[0]一定是0。
有同学问题那0 * 0 也算是一种啊为啥dp[0] 就是 0呢
看题目描述找到若干个完全平方数比如 1, 4, 9, 16, …题目描述中可没说要从0开始dp[0]0完全是为了递推公式。
非0下标的dp[j]应该是多少呢
从递归公式dp[j] min(dp[j - i * i] 1, dp[j]);中可以看出每次dp[j]都要选最小的所以非0下标的dp[j]一定要初始为最大值这样dp[j]在递推的时候才不会被初始值覆盖。
确定遍历顺序
我们知道这是完全背包
如果求组合数就是外层for循环遍历物品内层for遍历背包。
如果求排列数就是外层for遍历背包内层for循环遍历物品。
在动态规划322. 零钱兑换 (opens new window)中我们就深入探讨了这个问题本题也是一样的是求最小数
所以本题外层for遍历背包内层for遍历物品还是外层for遍历物品内层for遍历背包都是可以的
举例推导dp数组
已输入n为5例dp状态图如下
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IoGWI7QK-1690615913101)(https://code-thinking-1253855093.file.myqcloud.com/pics/20210202112617341.jpg “279.完全平方数”)]
代码
class Solution {public int numSquares(int n) {int dp[] new int[n 1];Arrays.fill(dp, Integer.MAX_VALUE);dp[0] 0;for(int i 1; i n 1; i){for(int j 1; j * j i; j){dp[i] Math.min(dp[i], dp[i - j * j] 1);}}return dp[n];}
}
