代码随想录算法训练营第44天（py）| 动态规划 | 322. 零钱兑换、279.完全平方数、139.单词拆分

本文主要是介绍代码随想录算法训练营第44天（py）| 动态规划 | 322. 零钱兑换、279.完全平方数、139.单词拆分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

322. 零钱兑换

力扣链接
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。

思路

每种硬币数量无限，是多重背包问题。

1. 确定dp含义
   凑到总金额为i的最少硬币个数为dp[i]
2. 确定递推公式
   凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]
   要凑j元，只需要加上一个钱币coins[i],即硬币个数为dp[j - coins[i]] + 1

dp[j] = min(dp[j - coins[i]] + 1,dp[j])

3. 初始化
   凑0元的硬币个数为0，因此dp[0]=0，其余元素初始化为最大的数。
4. 确定遍历方向
   由于只考虑个数，和顺序没关系，先遍历物品或者背包都可以。

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):dp[j] = min(dp[j - coin] + 1,dp[j])if dp[-1]==float('inf'): # 如果还是无穷大则无解return -1return dp[-1]

279.完全平方数

力扣链接
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

思路

和上一题很像，依旧是多重背包问题。不过coins数组要自己构建：

nums[i] = i * i

1. 确定dp含义
   和为j的完全平方数最少数量为dp[j]
2. 确定递推公式

dp[j] = min(dp[j - nums[i]] + 1,dp[j])

3. 初始化
   dp[0]=0，其余元素初始化为最大的数。
4. 确定遍历方向
   先遍历哪个都行

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

139.单词拆分

力扣链接
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词（可重复使用）拼接出 s 则返回 true。

思路

1. 确定dp含义
   对于子字符串[0:j]，dp[j]表示能否将该子字符串拆分。
2. 确定递推公式
   if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true
3. 初始化
   dp[0] = True，其余为False
4. 确定遍历方向
   字符串有顺序要求，求排列数就是外层for遍历背包，内层for循环遍历物品。

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] and s[j:i] in wordDict:dp[i] = True  break
# 如果 s[0:j] 可以被拆分成单词，并且 s[j:i] 在单词集合中存在，则 s[0:i] 可以被拆分成单词return dp[-1]

这篇关于代码随想录算法训练营第44天（py）| 动态规划 | 322. 零钱兑换、279.完全平方数、139.单词拆分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---