【代码随想录训练营】【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]