【代码随想录训练营】【Day 48】【动态规划-7】| 卡码 57， Leetcode 322， 279

【代码随想录训练营】【Day 48】【动态规划-7】| 卡码 57， Leetcode 322， 279

需强化知识点

• python 的幂次计算， 10 ** 5， 10 **（0.5）

题目

卡码 57. 爬楼梯（第八期模拟笔试）

• 注意 input 的读取

def func(n, m):# 爬到 i 楼的种类数dp = [0] * (n+1)dp[0] = 1for i in range(1, n+1):for j in range(1, m+1):if i >= j:dp[i] += dp[i-j]return dp[n]m, n = map(int, input().split())
print(func(m, n))

322. 零钱兑换

• 完全背包问题
• 注意 要判断 if dp[i-coin] != 10**5:

class Solution:def coinChange(self, coins: List[int], amount: int) -> int:# 组成金额 i 的最少硬币数dp = [10**5] * (amount+1)dp[0] = 0for coin in coins:for i in range(coin, amount+1):if dp[i-coin] != 10**5:dp[i] = min (dp[i], dp[i-coin] + 1)if dp[amount] == 10**5:return -1return dp[amount]

279. 完全平方数

• 完全背包问题

class Solution:def numSquares(self, n: int) -> int:dp = [float('inf')] * (n+1)dp[0] = 0for num in range(1, int(n ** (0.5))+1):for i in range( num*num, n+1):if dp[i - num*num] != float('inf'):dp[i] = min(dp[i], dp[i-num*num]+1)return dp[n]