代码随想录算法训练营 Day 33
Published:
动态规划五部曲
- 确定dp数组以及下标的含义
- 确定递推公式
- 初始化dp数组
- 确定遍历顺序
- 举例推导dp数组
第5步随着输入不同而变化，因此在此省去
Q1. LeetCode 322
注意：本题需要返回最小值和需要的硬币数量。转化为背包容量为amount，物品重量和价值均为coin_value
前四步：
- 使用一维的dp数组，dp[i]表示总金额为i时，最小需要的硬币数量
- 递推公式：总金额大于当前硬币面值，那么考虑是否将硬币加入，1. 如果用该硬币，那么需要找到凑出剩下金额所需要的最小硬币数量，即dp[i - coin_value]，并且加上当前硬币；2. 否则dp[i]不更新。因此 $dp[i] = min(dp[i], dp[i - coin_value] + 1)$
- 初始化：要找最小值，整个数组初始化为最大值，$dp[0]=0$代表不用任何硬币就能凑出0元
- 遍历顺序：从前向后遍历
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
n = len(coins)
# dp = [-1] * (amount + 1)
# dp[0] = 0
# for i in range(n):
# for j in range(amount + 1):
# if j >= coins[i]:
# if dp[j - coins[i]] != -1:
# if dp[j] != -1:
# dp[j] = min(dp[j], dp[j - coins[i]] + 1)
# else:
# dp[j] = dp[j - coins[i]] + 1
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(n):
for j in range(amount + 1):
if j >= coins[i]:
dp[j] = min(dp[j], dp[j - coins[i]] + 1)
if dp[-1] == float('inf'):
return -1
return dp[-1]
也可以将数组初始化为-1，更新dp数组时，如遇上-1，说明这是第一次发现能够用硬币组合出当前金额，那肯定也是最少数量
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
n = len(coins)
dp = [-1] * (amount + 1)
dp[0] = 0
for i in range(n):
for j in range(amount + 1):
if j >= coins[i]:
if dp[j - coins[i]] != -1:
if dp[j] != -1:
dp[j] = min(dp[j], dp[j - coins[i]] + 1)
else:
dp[j] = dp[j - coins[i]] + 1
return dp[-1]
复杂度分析
时间复杂度：O($amount \times n$) 空间复杂度：O($amount$)
Q2. LeetCode 279
转化为完全背包问题：背包容量为目标值，物品重量为$j^2$, 物品价值为$j$
前四步：
- 使用一维dp数组，dp[i]代表总和为i的组合最少有多少个完全平方数
- 递推公式：与Q1类似，$dp[i] = min(dp[i], dp[i - j^2] + 1$。
- 初始化：将整个dp数组初始化为最大值，$dp[0] = 0$因为没有任何组合总和为0
- 遍历顺序：从前向后遍历两层循环。因为物品的重量为$j^2$，所以注意第一层循环的终止条件
class Solution:
def numSquares(self, n: int) -> int:
dp = [float('inf')] * (n + 1)
dp[0] = 0
for i in range(int(n ** 0.5) + 1):
for j in range(n + 1):
if j >= i * i:
dp[j] = min(dp[j], dp[j - i * i] + 1)
return dp[-1]
复杂度分析
时间复杂度：O($n \times \sqrt{n}$) 空间复杂度：O($n$)
Q3. LeetCode 139
转化为完全背包：背包容量为目标字符串的长度，物品为字典中每个字符串
前四步：
- 使用一维dp数组，dp[i]代表长度为i时的子串是否可能是某些物品的排列
- 递推公式：要判断的条件有两个，假设字典中的字符串长度为j，那么首先需要判断从后往前取j位所构成的子串是否在字典中，然后还需要判断剩下的子串是否能够被字典中的字符串排列组成。$dp[i] = True$ if $dp[i - j] = True$ and $s[i-j:i] \in wordDict$
- 初始化：将整个dp数组初始化为0（False），$dp[0] = 1 （True）$因为不选任意一个字符串
- 遍历顺序：排列问题 - 需要先遍历目标字符串长度（背包），然后遍历字典中字符串（物品）
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
wordDict = set(wordDict)
dp = [0] * (len(s) + 1)
dp[0] = 1
for i in range(len(s) + 1):
for word in wordDict:
if len(word) <= i:
if dp[i - len(word)] and s[i - len(word):i] in wordDict:
dp[i] = 1
return dp[-1]
复杂度分析
时间复杂度：O($n \times 3$) 空间复杂度：O($n$) 取字符串的时间复杂度也为 O($n$)