LeetCode 第三十天2024.8.15

1. ：零钱兑换
 题目链接: 322. 零钱兑换 - 力扣（LeetCode）
应用条件：

难点：
# 确定dp数组（dp table）以及下标的含义：dp[j]表示凑成amount需要的硬币最少个数
# 确定递推公式: dp[j] min(dp[j-coins[i]]+1,dp[j])
# dp数组如何初始化:  dp[0]=0
# 确定遍历顺序: 组合先物品再背包 i从0到len(coins) j从0到amount

个人错误：

思路：

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

2. ：完全平方数
 题目链接: 279. 完全平方数 - 力扣（LeetCode）
应用条件：

难点：

# 确定dp数组（dp table）以及下标的含义：dp[j]表示和为 n 的完全平方数的最少数量 
# 确定递推公式: dp[j] min(dp[j-nums[i]]+1,dp[j])
# dp数组如何初始化:  dp[0]=0
# 确定遍历顺序: 组合先物品再背包 i从0到len(coins) j从0到amount+1

个人错误：

思路：

class Solution:def numSquares(self, n: int) -> int:nums = []for i in range( int(n ** 0.5) + 1):nums.append(i*i)dp = [float(inf)]*(n+1)dp[0] = 0# dp[1] = 1for i in range(len(nums)):for j in range(n+1):if j >= nums[i]:dp[j] = min(dp[j-nums[i]]+1,dp[j])print(dp)if dp[n] == float(inf):return -1else:return dp[n]

3. ：单词拆分
 题目链接: 139. 单词拆分 - 力扣（LeetCode）
应用条件：

难点：

# 确定dp数组（dp table）以及下标的含义：dp[j]表示长度到j的s能否被单词组成。 
# 确定递推公式: i从0到j 如果存在dp[i]是true以及dp[j-i]是true那么dp[j]也是true
# dp数组如何初始化:  dp[0]=true
# 确定遍历顺序: 这道题只能先背包再物品，因为物品有顺序，例如"apple" "pen" "apple"和"apple" "apple" "pen" 不一样 所以，j从0到len(s) i从0到j 

个人错误：

思路：

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 i in range(j):if dp[i] and (s[i:j] in wordDict):dp[j] = True break return dp[len(s)]