根據(jù)網(wǎng)站日志做seoseo就業(yè)前景
【代碼隨想錄訓練營】【Day 48】【動態(tài)規(guī)劃-7】| 卡碼 57， Leetcode 322， 279
需強化知識點
- python 的冪次計算， 10 ** 5， 10 **（0.5）
題目
卡碼 57. 爬樓梯（第八期模擬筆試）
- 注意 input 的讀取
def func(n, m):# 爬到 i 樓的種類數(shù)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 的最少硬幣數(shù)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. 完全平方數(shù)
- 完全背包問題
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]