代码随想录算法训练营第四十三天|动态规划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]=0 for 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 -1 return dp[amount] 279.完全平方数

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

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

代码随想录

class Solution: def numSquares(self, n: int) -> int: dp=[float('inf')]*(n+1) dp[0]=0 for 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]=True for 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)]