东莞哪里有网站建设厂家,seo排名优化怎么样,百姓网免费发布信息网下载,怎么做网站访问量KamaCoder 57. 爬楼梯 题目链接#xff1a;题目页面 (kamacoder.com)
这道题使用完全背包来实现#xff0c;我们首先考虑的是总的楼梯数#xff0c;因此dp数组大小为n 1 #xff0c;其意义是#xff0c;在n阶时有多少种方法爬到楼顶#xff0c;因此#xff0c;当前n状…KamaCoder 57. 爬楼梯 题目链接题目页面 (kamacoder.com)
这道题使用完全背包来实现我们首先考虑的是总的楼梯数因此dp数组大小为n 1 其意义是在n阶时有多少种方法爬到楼顶因此当前n状态等于前面状态(1, m)状态之和。
每道题都要考虑dp五步
1确定dp数组下标与值的关系满足凑出总楼梯的组合数
2确定递推公式我们把n个数组成看作1与n-1个组成,使用分而治之的思路来处理,dp[i] dp[i - j]
3确定初始值dp[0]为1,没得选
4确定遍历的数注意一下边界问题
5带入验证一下
代码
#python acm模式
while True:try:n, m map(int, input().split())dp [0 for _ in range(n 1)] //dp数组大小为n1dp[0] 1 //初始化dp[0]for i in range(1, n 1): //从1开始从0没意义for j in range(1, min(i, m) 1): //从前往后遍历可能的楼梯数dp[i] dp[i - j]print(dp[n])except:break LeetCode 322.零钱兑换 题目链接322. 零钱兑换 - 力扣LeetCode
这道题使用完全背包来实现要求的组成整数amount的最小硬币组合数因此dp数组大小为n 1 其意义是在n阶时最小的硬币数量因此当前n状态等于前面状态的最小值。
每道题都要考虑dp五步
1确定dp数组下标与值的关系满足凑出目标金额的最少硬币数量
2确定递推公式dp[i] min(dp[i], dp[i - coin] 1) (后面这个意思是从前coin的位置递推过来加上一个硬币数
3确定初始值dp[0]为0当目标为0时当然一个硬币也不要
4确定遍历的数注意一下i要大于等于当前coin否则数组会越界
5带入验证一下
代码
#python //DFS
class Solution:def coinChange(self, coins: List[int], amount: int) - int:dfsnlen(coins)cache //用一个装饰器def dfs(i,c):if i0: //判定结束条件return 0 if c0 else infif ccoins[i]: //确定一下coinreturn dfs(i-1,c)return min(dfs(i-1,c),dfs(i,c-coins[i])1) //返回最小的硬币数量递归resdfs(n-1,amount) //结果return res if resinf else -1 //看下结果呗要么有没有就-1
#python //二维DP
class Solution:def coinChange(self, coins: List[int], amount: int) - int:nlen(coins) //一共有n个硬币数量dp[[inf]*(amount1) for _ in range(n1)] //二维dp数组dp[0][0]0 //初始化一下for i,x in enumerate(coins): //使用枚举把键与值分离for c in range(amount1): //同样的是在金额内部if cx: //当前的值放不下硬币了dp[i1][c]dp[i][c]else: //放得下比较一下dp[i1][c]min(dp[i][c],dp[i][c-x]1)resdp[n][amount]return res if res inf else -1没有就-1
#python //一维DP
class Solution:def coinChange(self, coins: List[int], amount: int) - int:n len(coins)dp [float(inf) for _ in range(amount 1)]dp[0] 0for i in range(1, amount 1):for coin in coins:if i coin:dp[i] min(dp[i], dp[i - coin] 1)return dp[-1] if dp[-1] float(inf) else -1 LeetCode 279. 完全平方数 题目链接279. 完全平方数 - 力扣LeetCode
和前面的做法异曲同工注意一下范围就是
每道题都要考虑dp五步
1确定dp数组下标与值的关系满足凑出目标金额的最少完全平方数数量
2确定递推公式dp[i] min(dp[i], dp[i - j ** 2] 1) (后面这个意思是从前j**2的位置递推过来加上一个完全平方数
3确定初始值dp[0]为0当目标为0时当然完全平方数
4确定遍历的数注意一下i要大于等于当前j**2否则数组会越界
5带入验证一下
代码
#python 一维dp
class Solution:def numSquares(self, n: int) - int:dp [inf for _ in range(n 1)]dp[0] 0for i in range(1, n 1):for j in range(1, int(math.sqrt(i)) 1): //从小于当前i的平方根数来dp[i] min(dp[i], dp[i - (j ** 2)] 1)return dp[-1]
