本文主要是介绍代码随想录算法训练营day45| 70. 爬楼梯、322. 零钱兑换、279. 完全平方数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
70、爬楼梯：
class Solution(object):def climbStairs(self, n):""":type n: int:rtype: int"""dp = [0] * (n+1)dp[0] = 1steps = [1, 2]for j in range(n+1):for i in range(len(steps)):if j >= steps[i]:dp[j] += dp[j-steps[i]]return dp[n]抽象成完全背包问题也很简单，其实m阶的楼梯都可以这样做
322、零钱兑换：
class Solution(object):def coinChange(self, coins, amount):""":type coins: List[int]:type amount: int:rtype: int"""max_init = float('inf')dp = [max_init] * (amount + 1)dp[0] = 0for i in range(len(coins)):for j in range(coins[i], amount+1):dp[j] = min(dp[j], dp[j-coins[i]]+1)if dp[amount] == float('inf'):return -1return dp[amount]本题求的是装满背包最少的物品，核心递推公式为dp[j]=min(dp[j], dp[j-coins[i]]+1)，初始化dp[0]=0，注意排除组合不了的情况，返回-1
279、完全平方数：
class Solution(object):def numSquares(self, n):""":type n: int:rtype: int"""count = 0while count ** 2 <= n:count += 1nums = [i*i for i in range(1, count)]dp = [float('inf')] * (n + 1)dp[0] = 0for i in range(len(nums)):for j in range(nums[i], n+1):dp[j] = min(dp[j], dp[j-nums[i]]+1)return dp[n]本题和上题差不多，难点就是初始化，dp[0]=0
这篇关于代码随想录算法训练营day45| 70. 爬楼梯、322. 零钱兑换、279. 完全平方数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
