代码随想录算法训练营第四十三天| 动态规划06

322. 零钱兑换

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

这句话结合本题 大家要好好理解。

视频讲解：动态规划之完全背包，装满背包最少的物品件数是多少？| LeetCode：322.零钱兑换_哔哩哔哩_bilibili

代码随想录

class Solution:def coinChange(self, coins: List[int], amount: int) -> int:dp=[float('inf')]*(amount+1)dp[0]=0for coin in coins:for j in range(coin,amount+1):if dp[j-coin]!=float('inf'):dp[j]=min(dp[j-coin]+1,dp[j])if dp[amount]==float('inf'):return -1return dp[amount]

279.完全平方数

本题 和 322. 零钱兑换 基本是一样的，大家先自己尝试做一做

视频讲解：动态规划之完全背包，换汤不换药！| LeetCode：279.完全平方数_哔哩哔哩_bilibili

代码随想录

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

139.单词拆分

视频讲解：动态规划之完全背包，你的背包如何装满？| LeetCode：139.单词拆分_哔哩哔哩_bilibili

代码随想录

class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> bool:dp=[False]*(len(s)+1)dp[0]=Truefor j in range(1,len(s)+1):for word in wordDict:if j>=len(word):dp[j]=dp[j] or (dp[j-len(word)] and word==s[j-len(word):j])return dp[len(s)]