酒店网站建设方案,网站诚信建设,网站建设分什么行业,免费推广软件手机版文章目录 70. 爬楼梯 (进阶)322. 零钱兑换二维数组滚动数组 279. 完全平方数 70. 爬楼梯 (进阶)
题目链接 | 理论基础
以完全背包的思路来解题#xff0c;正如组合总和 Ⅳ 中提到的一样。在本题中#xff0c;先背包后物品的思路就显得非常合理明显了。
本题中的物品就是可… 文章目录 70. 爬楼梯 (进阶)322. 零钱兑换二维数组滚动数组 279. 完全平方数 70. 爬楼梯 (进阶)
题目链接 | 理论基础
以完全背包的思路来解题正如组合总和 Ⅳ 中提到的一样。在本题中先背包后物品的思路就显得非常合理明显了。
本题中的物品就是可以行走的步数 [1, 2]重量是 n可以重复选取步数求走到第 n 层有多少种走法。这样抽象过后就和组合总和 Ⅳ 一样是求排列了。
dp 的下标含义dp[j] 是到达第 j 层的方法数dp 递推公式dp[j] dp[j - i]dp 数组的初始化根据递推公式可以得知 dp[0]1 是必须的也符合前两层的结果其他的初始化为 0。dp 遍历顺序需要得到排列结果先背包后物品在爬楼梯的背景下就很合理举例推导省略
class Solution:def climbStairs(self, n: int) - int:choices [1, 2]# dp[i] represents the number of ways to reach position idp [0] * (n1)dp[0] 1# dp formulafor j in range(n1):for i in range(len(choices)):if j choices[i]:dp[j] dp[j-choices[i]]return dp[-1]本题看上去是个简单的爬楼梯但实际上是个简单的完全背包重要的是可以考验对物品和背包的遍历顺序的理解。事实上以后遇到排列的完全背包问题以爬楼梯的思路来理解会非常有效
322. 零钱兑换
题目链接 | 理论基础
本题和 零钱兑换II 非常相似依然是典型的完全背包问题。区别在于零钱兑换II 需要组合数这就规定了滚动数组的遍历顺序本题只需要最小组合数而不在乎得到该最小数的方式是组合或是排列。
二维数组 dp 数组的下标含义dp[i][j]使用硬币 [0, i] 组成金额 j 所使用的最小硬币数 dp 递推公式dp[i][j] min(dp[i-1][j], dp[i-1][j-coins[i]] 1) dp 的初始化本题的大坑 二维数组的初始化中 coins[0]i0和 j0 的情况是比较容易想到的 只能使用一个硬币时只有该硬币面值的整数倍金额 j 会初始化为 j // coins[0]当金额为 0 的时候不管有多少硬币可以使用都只需要 0 个硬币即可达成金额 0 那些不需要特殊初始化的位置才是需要小心的 由于题目要求“无法构成金额的情况返回 -1”自然想到应该优先把所有值初始化为 -1。这么做就会有下面第一种复杂的解法要考虑 min() 中每个元素为 -1 的情况堪称崩溃。由于 min() 的特性最好的初始化应该是 float(inf)这样不会影响后续的递推也不会影响初始化只需要在最后检查结果是否是 float(inf) 即可。如果被题目默认的初始化条件所迷惑而没有认识到 min() 的需求那就会踩坑虽然也能解决问题。 dp 的遍历顺序由于不需要排列二维数组可以解决物品和背包的顺序无所谓。 举例推导coins [1, 2, 5], amount 5 012345101234520112235011221
class Solution:def coinChange(self, coins: List[int], amount: int) - int:# dp[i][j] represents the smallest number to make j using coins [0, i]dp [[-1] * (amount 1) for _ in range(len(coins))]for j in range(amount 1):if j % coins[0] 0:dp[0][j] j // coins[0]for i in range(len(coins)):dp[i][0] 0# dp formulafor i in range(1, len(coins)):for j in range(amount 1):if j coins[i]:dp[i][j] dp[i-1][j]else:if dp[i-1][j] 0 and dp[i][j-coins[i]] 0:dp[i][j] min(dp[i-1][j], dp[i][j-coins[i]] 1)elif dp[i-1][j] -1 and dp[i][j-coins[i]] 0:dp[i][j] dp[i][j-coins[i]] 1elif dp[i-1][j] 0 and dp[i][j-coins[i]] -1:dp[i][j] dp[i-1][j]else:dp[i][j] -1return dp[-1][-1]正确初始化的解法
class Solution:def coinChange(self, coins: List[int], amount: int) - int:# dp[i][j] represents the smallest number to make j using coins [0, i]dp [[float(inf)] * (amount 1) for _ in range(len(coins))]for j in range(amount 1):if j % coins[0] 0:dp[0][j] j // coins[0]for i in range(len(coins)):dp[i][0] 0# dp formulafor i in range(1, len(coins)):for j in range(amount 1):if j coins[i]:dp[i][j] dp[i-1][j]else:dp[i][j] min(dp[i-1][j], dp[i][j-coins[i]] 1)return dp[-1][-1] if dp[-1][-1] ! float(inf) else -1滚动数组
之前做过的几道完全背包先物品后背包是求组合种类问题先背包后物品是求排列种类问题。如上所述本题只要求满足金额的硬币数不在意满足金额的结果的顺序所以物品、背包的遍历顺序都可以。
class Solution:def coinChange(self, coins: List[int], amount: int) - int:# dp[i][j] represents the smallest number to make j using coins [0, i]dp [-1] * (amount 1)dp[0] 0# dp formulafor i in range(len(coins)):for j in range(amount 1):if j coins[i]:if dp[j] 0 and dp[j-coins[i]] 0:dp[j] min(dp[j], dp[j-coins[i]] 1)elif dp[j] -1 and dp[j-coins[i]] 0:dp[j] dp[j-coins[i]] 1elif dp[j] 0 and dp[j-coins[i]] -1:dp[j] dp[j]else:dp[j] -1return dp[-1]正确初始化的解法
class Solution:def coinChange(self, coins: List[int], amount: int) - int:# dp[i][j] represents the smallest number to make j using coins [0, i]dp [float(inf)] * (amount 1)dp[0] 0# dp formulafor i in range(len(coins)):for j in range(amount 1):if j coins[i]:dp[j] min(dp[j], dp[j-coins[i]] 1)return dp[-1] if dp[-1] ! float(inf) else -1279. 完全平方数
题目链接 | 理论基础
本题乍一看和完全背包没什么关系。将完全平方数 149 … 看作是物品n 看作是背包容量的话就又是一道标准的完全背包问题求填满背包使用的最少物品数。抽象过后本题和上一题几乎是一模一样。
唯一的区别在于由于 n 的范围很大在 n 取较大值的时候会耗时较长。二维数组会直接超时而滚动数组也需要直接利用更新范围来减少遍历时间。这也是第一道二维数组无法解题的背包问题。
class Solution:def numSquares(self, n: int) - int:# dp[j] represents the number of ways to make jdp [float(inf)] * (n1)dp[0] 0max_sqrt_num int(sqrt(n))# dp formulafor i in range(max_sqrt_num):for j in range((i1) * (i1), n1):dp[j] min(dp[j], dp[j-(i1)*(i1)] 1)return dp[-1]
