代码随想录算法训练营第三十八天| 322. 零钱兑换 279.完全平方数 139.单词拆分
322. 零钱兑换
动态规划五部曲：
1.dp数组
dp[j]表示装满容量为j的背包，0-i硬币需要的最少个数
2.递推公式
dp[j] = min(dp[j],dp[j-coins[i]]+1)
3.初始化
dp[0]=0,dp[j]初始化最大值
4.遍历顺序，无所谓的
class Solution:def coinChange(self, coins: List[int], amount: int) -> int:dp = [0]*(amount+1)for j in range(1,amount+1):dp[j] = float('inf')for i in range(len(coins)):for j in range(amount+1):if j < coins[i]:dp[j]=dp[j]else:dp[j]=min(dp[j],dp[j-coins[i]]+1)return dp[-1] if dp[-1]!=float('inf') else -1279.完全平方数
动态规划五部曲：
1.dp数组
dp[j]表示装满背包为j 的数组，从0-i最少需要多少个数字
2.递推公式
dp[j] = min(dp[j],dp[j-num]+1)
3.初始化
dp[0]=1
4.遍历顺序，因为我们要求的是最小的数量，顺序是无所谓的
解析代码
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): # 遍历背包# 更新凑成数字 j 所需的最少完全平方数数量dp[j] = min(dp[j - i * i] + 1, dp[j])return dp[n]139.单词拆分
因为看到单词可以重复使用，因此考虑是完全背包问题
动态规划五部曲：
1.dp数组
dp[j] 表示，这里有点儿没想清楚，直接看看解析吧
dp[j]表示字符串长度为j，如果可以拆分，则为True，如果不行则为False
2.递推公式
dp[j]
如果说dp[i]是True而且，[i,j]之间的子串出现在字典里面，那么就是True
3.除了dp[0]都是false
4.遍历顺序，也无所谓
为什么这里解析里面写的是排列问题呢，难道能组成这个不是个组合问题么
class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> bool:dp = [False]*(len(s)+1)dp[0]=Truefor i in range(1,len(s)+1):for j in range(i):if dp[j]==True and s[j:i] in wordDict:dp[i] = Truereturn dp[-1]我感觉这个遍历顺序的关系，不是因为是排列还是组合问题，而是因为包含问题
class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> bool:dp = [False]*(len(s)+1)dp[0]=Truefor i in range(len(s)+1):for j in range(i+1,len(s)+1):#这里要确定下j的遍历范围if dp[i]==True and s[i:j] in wordDict:dp[j] = Truereturn dp[-1]