这道题简直和上一个系列的最后一题如出一撤。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
# 初始化dp数组
dp = [0]*(target+1)
# dp数组初始化赋值
dp[0] = 1
# 开始循环，因为所求为排列问题，最关键的一句话是
# 顺序不同的序列被视作不同的组合
# 所以遍历顺序是先遍历背包，再遍历物品
# 下面i这里，第一次写的时候，忘记从1开始遍历， 是从0开始的
# 不过我们已经初始化了，所以不影响结果
for i in range(1,target+1):
for j in range(len(nums)):
if i >= nums[j]:
dp[i] += dp[i-nums[j]]
return dp[target]
一点感悟：在做本题时，有一点错觉，dp数组的含义是没有异议的，但是因为题目说，不同顺序的排列算作不同的组合，那么加入target=4，当前遍历物品重量为1，则dp[4] += dp[4-1]，假如dp[3]中的方式为[3]，那么1加入其中，应该有[1,3] [3,1]两种顺序啊，不应该是dp[3]再加某个值吗？
答：不是的！这种情况会造成重复，在我们的代码编写中，物品是按照顺序遍历的，上述dp[4] += dp[4-1]，得到的排列就是[3,1] , 就是这一种情况，而[1,3]的情况，则在我们遍历到物品3时，由dp[4] += dp[4-3]得到！
本题和上一篇博客的最后一题，可谓是相辅相成了，这里放上本篇的链接，值得细读。
拓展：我们在上一篇博客，写到了一个爬楼梯问题，如果问题改成，一次可以爬最多M个台阶，求能到达楼顶的方法的个数。
和本题是一模一样的！也是求排列数。
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
dp = [0] * (target + 1) # 创建动态规划数组，用于存储组合总数
dp[0] = 1 # 初始化背包容量为0时的组合总数为1
for i in range(1, target + 1): # 遍历背包容量
for j in nums: # 遍历物品列表
if i >= j: # 当背包容量大于等于当前物品重量时
dp[i] += dp[i - j] # 更新组合总数
return dp[-1] # 返回背包容量为target时的组合总数
过。
运行错误的二维DP代码
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
n = len(nums)
dp = [[0]*(target + 1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(n+1):
dp[i][0] = 1
'''
for j in range(target+1):
dp[0][j] = 1
'''
for j in range(1, target+1):
for i in range(1,n+1) :
dp[i][j] = dp[i-1][j]
if j >= nums[i-1] :
dp[i][j] += dp[i][j-nums[i-1]]
return dp[-1][-1]
放上代码随想录的解答链接。
爬楼梯进阶
能想到爬楼梯问题，问一共有多少种方法，可以看做，完全背包+求排列数。
写出来了，完全按照动归五部曲做的，写完这道题体会到动归五部曲真好用。
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [inf]*(amount+1)
dp[0] = 0
for i in range(1,amount+1):
for j in range(len(coins)):
if i >= coins[j]:
dp[i] = min(dp[i],dp[i-coins[j]]+1)
if dp[amount]==inf :
return -1
else :
return dp[amount]
做动态规划的题目，有时候不需要先把整道题的思路全部想通，一步一步来就好，就按照动归五部曲，这道题一开始我也想不通，不知道为什么背包问题求的是最大，这里求最小怎么弄。
不用管，直接上动归五部曲，求最大，在递推公式那里就是max运算符，求最小，在递推公式那里，就是min运算符。
第一步：确定dp数组的含义，题目求什么就定义为什么，也别想太多，dp[i]定义为：amount为 i 时，所需要的硬币的最小个数。
第二步：确定递推公式，这里按照dp数组的定义，很容易想到，dp[i] = min( dp[i] , dp[i-coins[j]] )
第三步：初始化。这里很重要，也是很容易错的地方。初始化的值和前两步息息相关。一开始我这里就定义错了。 dp[0] = 0 , 因为此时没有硬币组合可以是0，那么 dp[i] 呢 ？ 因为递推公式是求min，为了避免初始化对操作符的影响，这里应该初始化为最大值！一开始我想的是初始化为-1，但是这样的话，最后的数组依旧全是-1
第四步：确定遍历顺序。本题求钱币最小个数，那么钱币有顺序和没有顺序都可以，都不影响钱币的最小个数。所以本题并不强调集合是组合还是排列。如果求组合数就是外层for循环遍历物品，内层for遍历背包。如果求排列数就是外层for遍历背包，内层for循环遍历物品。因为{ 5 5 1} 和 { 5 1 5}的钱币个数都是3。我这里的遍历顺序是先遍历的背包，不过感觉也许先遍历物品，更符合习惯。完全背包问题，背包为正序遍历。
第五步：模拟，打印dp数组。
先遍历物品 后遍历背包
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [float('inf')] * (amount + 1) # 创建动态规划数组，初始值为正无穷大
dp[0] = 0 # 初始化背包容量为0时的最小硬币数量为0
for coin in coins: # 遍历硬币列表，相当于遍历物品
for i in range(coin, amount + 1): # 遍历背包容量
if dp[i - coin] != float('inf'): # 如果dp[i - coin]不是初始值，则进行状态转移
dp[i] = min(dp[i - coin] + 1, dp[i]) # 更新最小硬币数量
if dp[amount] == float('inf'): # 如果最终背包容量的最小硬币数量仍为正无穷大，表示无解
return -1
return dp[amount] # 返回背包容量为amount时的最小硬币数量
先遍历物品 后遍历背包（优化版）
这个剪枝操作还可以。
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for i in range(coin, amount + 1): # 进行优化，从能装得下的背包开始计算，则不需要进行比较
# 更新凑成金额 i 所需的最少硬币数量
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
本题首先明确，是完全背包问题，不要求遍历顺序，那么一维DP数组的代码就很好写了。
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [inf]*(amount+1)
dp[0] = 0
for i in range(len(coins)):
for j in range(coins[i],amount+1):
dp[j] = min(dp[j],dp[j-coins[i]]+1)
if dp[amount]==inf :
return -1
else :
return dp[amount]
进阶，写个二维DP数组的。
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
n = len(coins)
dp = [[inf]*(amount+1) for _ in range(n+1)]
# 二维需要注意的地方真多啊，初始化要考虑的更全面
dp[0][0] = 0
for i in range(n+1):
dp[i][0] = 0
# 当没有硬币时，想要凑成 amount 是不可能的，所以不是0，而是 inf
'''
for i in range(amount+1):
dp[0][i] = 0
'''
for i in range(1,n+1):
# 注意 j 不是从 coins[i-1] 开始，而是从 1 开始
for j in range(1,amount+1):
# 注意这里必须要有判断
if j < coins[i-1]:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = min(dp[i-1][j],dp[i][j-coins[i-1]]+1)
if dp[-1][-1]==inf :
return -1
else :
return dp[-1][-1]
和上一题差不多，本题考虑到如果物品数组也给 [1,n] 的话，两个循环时间复杂度就是O(n^2)了，那么不如先把可能选择的完全平方数先算出来。
class Solution:
def numSquares(self, n: int) -> int:
items = []
for i in range(1,int(sqrt(n))+2):
if i*i <= n :
items.append(i*i)
m = len(items)
dp = [inf]*(n+1)
dp[0] = 0
for i in range(m):
for j in range(items[i],n+1):
dp[j] = min(dp[j],dp[j-items[i]]+1)
return dp[n]
没啥好说的，寻找可选的完全平方数的过程，也可以直接放在双重循环里。
本题依然求得是，最少的个数的数量，所以不管是组合方式还是排列方式，均可以，所以在遍历顺序上不做要求。
先遍历物品, 再遍历背包
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): # 遍历背包
# 更新凑成数字 j 所需的最少完全平方数数量
dp[j] = min(dp[j - i * i] + 1, dp[j])
return dp[n]
过。
这周稍微对动态规划有点感觉了。
没思路。
这道题，代码随想录写的解答很好，其给出的回溯算法也要进行学习，相当于回忆知识了。
本题的dp数组的构思，递推公式的推导，初始化的选择，遍历顺序的确定，每一步都不容易，每一步都容易错！
回溯
class Solution:
def backtracking(self, s: str, wordSet: set[str], startIndex: int) -> bool:
# 边界情况：已经遍历到字符串末尾，返回True
if startIndex >= len(s):
return True
# 遍历所有可能的拆分位置
for i in range(startIndex, len(s)):
word = s[startIndex:i + 1] # 截取子串
if word in wordSet and self.backtracking(s, wordSet, i + 1):
# 如果截取的子串在字典中，并且后续部分也可以被拆分成单词，返回True
return True
# 无法进行有效拆分，返回False
return False
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
wordSet = set(wordDict) # 转换为哈希集合，提高查找效率
return self.backtracking(s, wordSet, 0)
DP（版本一）
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
wordSet = set(wordDict)
n = len(s)
dp = [False] * (n + 1) # dp[i] 表示字符串的前 i 个字符是否可以被拆分成单词
dp[0] = True # 初始状态，空字符串可以被拆分成单词
for i in range(1, n + 1): # 遍历背包
for j in range(i): # 遍历单词
if dp[j] and s[j:i] in wordSet:
dp[i] = True # 如果 s[0:j] 可以被拆分成单词，并且 s[j:i] 在单词集合中存在，则 s[0:i] 可以被拆分成单词
break
return dp[n]
DP（版本二）
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)]
下面这个代码很好理解
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)]
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n = len(wordDict)
dp = [[False]*(len(s) + 1) for _ in range(n+1)]
dp[0][0] = True
for i in range(n+1):
dp[i][0] = True
for j in range(1, len(s) + 1):
for i in range(1,n+1) :
if j < len(wordDict[i-1]):
dp[i][j] = dp[i-1][j]
else :
flag = dp[i][j-len(wordDict[i-1])] and wordDict[i-1] == s[j-len(wordDict[i-1]):j]
dp[i][j] = dp[i-1][j] or flag
return dp[-1][-1]
多加一个循环，遍历物品个数即可，我不喜欢，展开成背包问题的写法。同时，此题也告诉了我们：01背包中的物品，可以是相同的。
def test_multi_pack():
weight = [1, 3, 4]
value = [15, 20, 30]
nums = [2, 3, 2]
bagWeight = 10
dp = [0] * (bagWeight + 1)
for i in range(len(weight)): # 遍历物品
for j in range(bagWeight, weight[i] - 1, -1): # 遍历背包容量
# 以上为01背包，然后加一个遍历个数
for k in range(1, nums[i] + 1): # 遍历个数
if j - k * weight[i] >= 0:
dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i])
# 打印一下dp数组
for j in range(bagWeight + 1):
print(dp[j], end=" ")
print()
print(dp[bagWeight])
test_multi_pack()
def test_multi_pack(weight, value, nums, bagWeight):
dp = [0] * (bagWeight + 1)
for i in range(len(weight)): # 遍历物品
for j in range(bagWeight, weight[i] - 1, -1): # 遍历背包容量
# 以上为01背包，然后加一个遍历个数
for k in range(1, nums[i] + 1): # 遍历个数
if j - k * weight[i] >= 0:
dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i])
# 使用 join 函数打印 dp 数组
print(' '.join(str(dp[j]) for j in range(bagWeight + 1)))
print(dp[bagWeight])
if __name__ == "__main__":
weight = [1, 3, 4]
value = [15, 20, 30]
nums = [2, 3, 2]
bagWeight = 10
test_multi_pack(weight, value, nums, bagWeight)
背包问题结束啦，代码随想录对不同问题进行了不同角度的分类，用来复习真的很棒。
背包问题总结篇
依旧是按照五部曲来分析的。
dp数组的含义 ： 考虑到第 i 个房屋，包含第 i 个房屋，所能偷的最大金额。
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
dp = [0]*(n+1)
dp[1] = nums[0]
for i in range(2,n+1):
dp[i] = max(dp[i-1],dp[i-2]+nums[i-1])
return dp[n]
目前感觉自己做动态规划类的题目，有一个问题就是，对dp数组的含义有非常大的执著，总觉得要将其定义为一个看上去非常合理的量，认为这是求解问题的基础。
但是其实根本不必！就是，题目问什么，就定义什么就好，有的问题再适当做一点改变和限制就好。
dp数组的定义不用太纠结，dp数组定义的很抽象，靠递推关系也可以使状态转移进行的很明朗。
本题其实我多考虑了一个无用状态 dp[0] ，因为在我的定义中，i 是代表第 i 个房屋，而房屋下标的开始就是1. 在代码随想录的讲解中，i 是代表下标为 i 为房屋，这样就可以从0开始了，不过我这样初始化好像更简单一些。
dp[i] 仅仅是考虑到第 i 个房屋，不考虑偷与不偷，偷与不偷，通过递推公式去考虑，而不是代表偷第 i 个房屋。在dp定义中，显示地考虑每个房间偷与不偷状态的数组，为二维dp数组。
像我对本题dp数组的定义方式，还是不如代码随想录中给出的，这一点在下一题就有所体现，如果所有房屋组成了一个环，那么我就不能在前面硬生生加入一个dp[0]了，还是要按照房屋下标去考虑。
1维DP
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) == 0: # 如果没有房屋，返回0
return 0
if len(nums) == 1: # 如果只有一个房屋，返回其金额
return nums[0]
# 创建一个动态规划数组，用于存储最大金额
dp = [0] * len(nums)
dp[0] = nums[0] # 将dp的第一个元素设置为第一个房屋的金额
dp[1] = max(nums[0], nums[1]) # 将dp的第二个元素设置为第一二个房屋中的金额较大者
# 遍历剩余的房屋
for i in range(2, len(nums)):
# 对于每个房屋，选择抢劫当前房屋和抢劫前一个房屋的最大金额
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
return dp[-1] # 返回最后一个房屋中可抢劫的最大金额
2维DP
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums: # 如果没有房屋，返回0
return 0
n = len(nums)
dp = [[0, 0] for _ in range(n)] # 创建二维动态规划数组，dp[i][0]表示不抢劫第i个房屋的最大金额，dp[i][1]表示抢劫第i个房屋的最大金额
dp[0][1] = nums[0] # 抢劫第一个房屋的最大金额为第一个房屋的金额
for i in range(1, n):
dp[i][0] = max(dp[i-1][0], dp[i-1][1]) # 不抢劫第i个房屋，最大金额为前一个房屋抢劫和不抢劫的最大值
dp[i][1] = dp[i-1][0] + nums[i] # 抢劫第i个房屋，最大金额为前一个房屋不抢劫的最大金额加上当前房屋的金额
return max(dp[n-1][0], dp[n-1][1]) # 返回最后一个房屋中可抢劫的最大金额
优化版
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums: # 如果没有房屋，返回0
return 0
prev_max = 0 # 上一个房屋的最大金额
curr_max = 0 # 当前房屋的最大金额
for num in nums:
temp = curr_max # 临时变量保存当前房屋的最大金额
curr_max = max(prev_max + num, curr_max) # 更新当前房屋的最大金额
prev_max = temp # 更新上一个房屋的最大金额
return curr_max # 返回最后一个房屋中可抢劫的最大金额
过。
没写出来，被环形房屋卡住了，纠结在于怎样处理第0个和第n个之间的关系。
错误代码中的定义：dp[i][0] : 没偷第0个，包括第 i 个房屋，所能获得的最大金币。dp[i][1] : 偷第0个，包括第 i 个房屋，所能获得的最大金币。
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
dp = [[0]*2 for _ in range(n)]
dp[0][0] = 0
dp[0][1] = nums[0]
dp[1][0] = nums[1]
dp[1][1] = nums[0]
for i in range(2,n):
dp[i][0] = max(dp[i-1][0],dp[i-2][0]+nums[i])
dp[i][1] = dp[i-1][1]
return max(dp[n-1])
我这个错误的代码，打印一下dp数组，就可以明显看出错误。思考了一下应该没得改，这种dp数组的定义方式就是错误的，带有全局意义的变量，不能将某一个元素的特性赋给它。
还是思考方向错了，直接暴力区分，考虑首元素不考虑尾元素，考虑尾元素不考虑首元素，两种逻辑即可。说白了就是上一题的逻辑跑两遍，每次传入的房间数组，分别是去除尾元素和去除首元素的，然后取最大即可。
解决环的问题，分情况讨论。
环形问题，使我们找不到起始位置，要考虑将环形问题展开，展开为线性问题。
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
if len(nums) == 1:
return nums[0]
result1 = self.robRange(nums, 0, len(nums) - 2) # 情况二
result2 = self.robRange(nums, 1, len(nums) - 1) # 情况三
return max(result1, result2)
# 198.打家劫舍的逻辑
def robRange(self, nums: List[int], start: int, end: int) -> int:
if end == start:
return nums[start]
prev_max = nums[start]
curr_max = max(nums[start], nums[start + 1])
for i in range(start + 2, end + 1):
temp = curr_max
curr_max = max(prev_max + nums[i], curr_max)
prev_max = temp
return curr_max
2维DP
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) < 3:
return max(nums)
# 情况二：不抢劫第一个房屋
result1 = self.robRange(nums[:-1])
# 情况三：不抢劫最后一个房屋
result2 = self.robRange(nums[1:])
return max(result1, result2)
def robRange(self, nums):
dp = [[0, 0] for _ in range(len(nums))]
dp[0][1] = nums[0]
for i in range(1, len(nums)):
dp[i][0] = max(dp[i - 1])
dp[i][1] = dp[i - 1][0] + nums[i]
return max(dp[-1])
优化版
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums: # 如果没有房屋，返回0
return 0
if len(nums) == 1: # 如果只有一个房屋，返回该房屋的金额
return nums[0]
# 情况二：不抢劫第一个房屋
prev_max = 0 # 上一个房屋的最大金额
curr_max = 0 # 当前房屋的最大金额
for num in nums[1:]:
temp = curr_max # 临时变量保存当前房屋的最大金额
curr_max = max(prev_max + num, curr_max) # 更新当前房屋的最大金额
prev_max = temp # 更新上一个房屋的最大金额
result1 = curr_max
# 情况三：不抢劫最后一个房屋
prev_max = 0 # 上一个房屋的最大金额
curr_max = 0 # 当前房屋的最大金额
for num in nums[:-1]:
temp = curr_max # 临时变量保存当前房屋的最大金额
curr_max = max(prev_max + num, curr_max) # 更新当前房屋的最大金额
prev_max = temp # 更新上一个房屋的最大金额
result2 = curr_max
return max(result1, result2)
过。
超出时间限制，代码思路是代码随想录中的暴力递归版。
class Solution:
def rob(self, root: Optional[TreeNode]) -> int:
if root == None :
return 0
if root.left == None and root.right == 0:
return root.val
left = self.rob(root.left)
right = self.rob(root.right)
if left == 0 and right == 0 :
return root.val
elif left == 0 and right != 0 :
return max(root.val+self.rob(root.right.left)+self.rob(root.right.right),right)
elif left != 0 and right == 0 :
return max(root.val+self.rob(root.left.left)+self.rob(root.left.right),left)
else :
return max(root.val+self.rob(root.left.left)+self.rob(root.left.right)+self.rob(root.right.left)+self.rob(root.right.right),left+right)
代码随想录给出的博文中，分析了暴力递归超时的原因，许多节点的状态被重复计算了，进而给出解决方案，用两个维度去记录当前节点的状态！
这是我没想到的。
本题的解答博文中，还涉及了记忆化递归的过程，这个在之前应该是没有讲过的(虽然卡哥说他讲过了)，看了看代码，其实就是维护一个字典，来储存已经算过的子串，代码上也很好理解，在递归函数一开始判断那里，加上 if 存在 就 return . 递归结束有了值，就加入字典。
本题是一个树形DP的入门题，要学习！放上代码随想录的解答博文链接。
注意，本题的dp数组，其实就是一个一维的数组，而且长度为2，就表示当前节点的状态，偷与不偷，不需要去定义包含所有节点的dp数组，因为在递归过程中，每一次递归都会有一个相应的dp数组存在。
暴力递归
class Solution:
def rob(self, root: TreeNode) -> int:
if root is None:
return 0
if root.left is None and root.right is None:
return root.val
# 偷父节点
val1 = root.val
if root.left:
val1 += self.rob(root.left.left) + self.rob(root.left.right)
if root.right:
val1 += self.rob(root.right.left) + self.rob(root.right.right)
# 不偷父节点
val2 = self.rob(root.left) + self.rob(root.right)
return max(val1, val2)
记忆化递归
class Solution:
memory = {}
def rob(self, root: TreeNode) -> int:
if root is None:
return 0
if root.left is None and root.right is None:
return root.val
if self.memory.get(root) is not None:
return self.memory[root]
# 偷父节点
val1 = root.val
if root.left:
val1 += self.rob(root.left.left) + self.rob(root.left.right)
if root.right:
val1 += self.rob(root.right.left) + self.rob(root.right.right)
# 不偷父节点
val2 = self.rob(root.left) + self.rob(root.right)
self.memory[root] = max(val1, val2)
return max(val1, val2)
动态规划
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rob(self, root: Optional[TreeNode]) -> int:
# dp数组（dp table）以及下标的含义：
# 1. 下标为 0 记录 **不偷该节点** 所得到的的最大金钱
# 2. 下标为 1 记录 **偷该节点** 所得到的的最大金钱
dp = self.traversal(root)
return max(dp)
# 要用后序遍历, 因为要通过递归函数的返回值来做下一步计算
def traversal(self, node):
# 递归终止条件，就是遇到了空节点，那肯定是不偷的
if not node:
return (0, 0)
left = self.traversal(node.left)
right = self.traversal(node.right)
# 不偷当前节点, 偷子节点
# 子节点偷不偷，决定于哪个值更大
val_0 = max(left[0], left[1]) + max(right[0], right[1])
# 偷当前节点, 不偷子节点
val_1 = node.val + left[0] + right[0]
return (val_0, val_1)
一定要多练习，这道题。
解答错误，错在无法明确股票是在哪一天买入和卖出的，在递推公式上，就会出现错误和混乱。
错误的dp数组含义：在前 i 天买入卖出所得的最大金钱。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
dp = [0]*len(prices)
dp[0]=-inf
dp[1]=prices[1]-prices[0]
for i in range(2,len(prices)):
temp = [dp[i-1],dp[i-1]-prices[i-1]+prices[i],prices[i]-prices[i-1]]
dp[i] = max(temp)
print(dp)
return dp[len(prices)-1]
又想了想，想出了一个自己觉得就很垃圾的方案。
dp数组含义：在第 i 天卖出所得的最大金钱。在本题中，初始化同样需要注意，本题的示例中已说明，如果没有交易完成，return 0 。同样的，要首先判断一下 prices 数组是不是只有一个值，一个值也要return 0。在我的定义下，对于dp[0]可以不做初始化，因为这种情况是非法的，而且我在前面已经做了 if 判断。
我这个方法最后还要对dp数组取一个max
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices)==1:
return 0
dp = [0]*len(prices)
dp[1]=prices[1]-prices[0]
for i in range(2,len(prices)):
temp = [dp[i-1]-prices[i-1]+prices[i],prices[i]-prices[i-1]]
dp[i] = max(temp)
return max(dp)
本题还有一个很朴素的贪心法。因为股票就买卖一次，那么贪心的想法很自然就是取最左最小值，取最右最大值，那么得到的差值就是最大利润。
跟股票买卖有关的问题，dp数组的定义，基本都是从本题定义的基础上演变过去的。还是要学习代码随想录这一套定义dp数组的方法的，我的那种方法可能只能解决这一道题，不具有普适性。
本题的初始化也是需要理解的。
贪心法：
class Solution:
def maxProfit(self, prices: List[int]) -> int:
low = float("inf")
result = 0
for i in range(len(prices)):
low = min(low, prices[i]) #取最左最小价格
result = max(result, prices[i] - low) #直接取最大区间利润
return result
动态规划：版本一
class Solution:
def maxProfit(self, prices: List[int]) -> int:
length = len(prices)
if len == 0:
return 0
dp = [[0] * 2 for _ in range(length)]
dp[0][0] = -prices[0]
dp[0][1] = 0
for i in range(1, length):
dp[i][0] = max(dp[i-1][0], -prices[i])
dp[i][1] = max(dp[i-1][1], prices[i] + dp[i-1][0])
return dp[-1][1]
动态规划：版本二
class Solution:
def maxProfit(self, prices: List[int]) -> int:
length = len(prices)
dp = [[0] * 2 for _ in range(2)] #注意这里只开辟了一个2 * 2大小的二维数组
dp[0][0] = -prices[0]
dp[0][1] = 0
for i in range(1, length):
dp[i % 2][0] = max(dp[(i-1) % 2][0], -prices[i])
dp[i % 2][1] = max(dp[(i-1) % 2][1], prices[i] + dp[(i-1) % 2][0])
return dp[(length-1) % 2][1]
动态规划：版本三
class Solution:
def maxProfit(self, prices: List[int]) -> int:
length = len(prices)
dp0, dp1 = -prices[0], 0 #注意这里只维护两个常量，因为dp0的更新不受dp1的影响
for i in range(1, length):
dp1 = max(dp1, dp0 + prices[i])
dp0 = max(dp0, -prices[i])
return dp1
过。
代码随想录的博文总结的很好。
这道题用上一题我的dp数组定义就行不通了。
所以还是学习代码随想录定义的dp数组含义吧。
借鉴了上一题，代码随想录的dp数组定义，本题只改变了递推逻辑的部分。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
length = len(prices)
if len == 0 or len(prices)==1:
return 0
dp = [[0] * 2 for _ in range(length)]
dp[0][0] = -prices[0]
dp[0][1] = 0
for i in range(1,length):
dp[i][0] = max(dp[i-1][1]-prices[i],dp[i-1][0])
dp[i][1] = max(dp[i-1][0]+prices[i],dp[i-1][1])
return dp[length-1][1]
本题是股票可以买卖多次，上一题，股票只能买卖一次。注意体会两题的区别。其他，诸如：dp数组的含义，以及dp数组的初始化问题，都是一样的。
版本一：
class Solution:
def maxProfit(self, prices: List[int]) -> int:
length = len(prices)
dp = [[0] * 2 for _ in range(length)]
dp[0][0] = -prices[0]
dp[0][1] = 0
for i in range(1, length):
dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]) #注意这里是和121. 买卖股票的最佳时机唯一不同的地方
dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])
return dp[-1][1]
版本二：
class Solution:
def maxProfit(self, prices: List[int]) -> int:
length = len(prices)
dp = [[0] * 2 for _ in range(2)] #注意这里只开辟了一个2 * 2大小的二维数组
dp[0][0] = -prices[0]
dp[0][1] = 0
for i in range(1, length):
dp[i % 2][0] = max(dp[(i-1) % 2][0], dp[(i-1) % 2][1] - prices[i])
dp[i % 2][1] = max(dp[(i-1) % 2][1], dp[(i-1) % 2][0] + prices[i])
return dp[(length-1) % 2][1]
过。
依旧根据前面两题的逻辑思维。要注意的是，本来我想在二维数组后面再加一维，来表示当前是第几次购买的状态，但是三维数组可能在声明上不太方便了，于是就按照代码随想录中的做法，把第三维压缩进第二维了，这样写法也挺好的，也很清晰明了。
本题的dp数组定义不需要变化，只要明确定义4个状态就好，需要注意的是初始值的状态，这里我就在第一次提交时，出错了。
就是第0天第二次持有的状态下，所拥有的最大金钱数，应该和第0天第一次持有的状态，相同，均为 -prices[0] 。 表示当天买入-卖出-买入。一开始我这里设置为0了，产生错误。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
if n==0 or n==1:
return 0
dp = [[0]*4 for _ in range(n)]
dp[0][0] = -prices[0]
dp[0][1] = 0
dp[0][2] = -prices[0]
dp[0][3] = 0
for i in range(1,n):
dp[i][0] = max(dp[i-1][0],-prices[i])
dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i])
dp[i][2] = max(dp[i-1][2],dp[i-1][1]-prices[i])
dp[i][3] = max(dp[i-1][3],dp[i-1][2]+prices[i])
return max(dp[n-1][1],dp[n-1][3])
就是定义四个状态，从来没想过定义一个0状态。
这里不做什么记录了，放上代码随想录的链接。
买卖股票的最佳时机 III
有一点需要学习的地方：
最大的时候一定是卖出的状态，而两次卖出的状态现金最大一定是最后一次卖出。如果想不明白的录友也可以这么理解：如果第一次卖出已经是最大值了，那么我们可以在当天立刻买入再立刻卖出。所以dp[n][4]已经包含了dp[n][2]的情况。也就是说第二次卖出手里所剩的钱一定是最多的。
版本一：
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) == 0:
return 0
dp = [[0] * 5 for _ in range(len(prices))]
dp[0][1] = -prices[0]
dp[0][3] = -prices[0]
for i in range(1, len(prices)):
dp[i][0] = dp[i-1][0]
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i])
dp[i][3] = max(dp[i-1][3], dp[i-1][2] - prices[i])
dp[i][4] = max(dp[i-1][4], dp[i-1][3] + prices[i])
return dp[-1][4]
版本二：
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) == 0:
return 0
dp = [0] * 5
dp[1] = -prices[0]
dp[3] = -prices[0]
for i in range(1, len(prices)):
dp[1] = max(dp[1], dp[0] - prices[i])
dp[2] = max(dp[2], dp[1] + prices[i])
dp[3] = max(dp[3], dp[2] - prices[i])
dp[4] = max(dp[4], dp[3] + prices[i])
return dp[4]
过。
同样的，就是上一题的简单拓展，但这里，我觉得我自己对在遍历中的第1次买入，也就是index为0的操作，有些冗余，我是用一个 if 条件去单独判断的。不知道代码随想录中怎么写。
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
n = len(prices)
if n==0 or n==1:
return 0
m = int(k*2)
dp = [[0]*m for _ in range(n)]
for i in range(m):
if i %2 == 0:
dp[0][i] = -prices[0]
for i in range(1,n):
for j in range(m):
if j % 2 == 0:
if j == 0 :
dp[i][j] = max(dp[i-1][j],-prices[i])
else :
dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]-prices[i])
else :
dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]+prices[i])
return dp[n-1][m-1]
代码随想录对上述我提到的问题的解决方法是：多定义一个状态0，贯穿始终，始终不变，一直为0 。
版本一
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
if len(prices) == 0:
return 0
dp = [[0] * (2*k+1) for _ in range(len(prices))]
for j in range(1, 2*k, 2):
dp[0][j] = -prices[0]
for i in range(1, len(prices)):
for j in range(0, 2*k-1, 2):
dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j] - prices[i])
dp[i][j+2] = max(dp[i-1][j+2], dp[i-1][j+1] + prices[i])
return dp[-1][2*k]
版本二
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
if len(prices) == 0: return 0
dp = [0] * (2*k + 1)
for i in range(1,2*k,2):
dp[i] = -prices[0]
for i in range(1,len(prices)):
for j in range(1,2*k + 1):
if j % 2:
dp[j] = max(dp[j],dp[j-1]-prices[i])
else:
dp[j] = max(dp[j],dp[j-1]+prices[i])
return dp[2*k]
过。
我还是对上一题的思路，稍加修改，先算出了最大的K值，但是这样的后果就是，不管是时间还是占用内存上，均只击败了5%的用户。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
if n==0 or n==1:
return 0
k = (n//3)+1
m = int(k*2)
dp = [[0]*m for _ in range(n)]
for i in range(m):
if i %2 == 0:
dp[0][i] = -prices[0]
for i in range(1,n):
for j in range(m):
if j % 2 == 0:
if j == 0 :
dp[i][j] = max(dp[i-1][j],-prices[i])
else :
dp[i][j] = max(dp[i-1][j],dp[i-2][j-1]-prices[i])
else :
dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]+prices[i])
return dp[n-1][m-1]
买卖K次那个题没办法，必须定义那么多状态，但是对于本题，其实只要定义4个状态就可以了，去学习代码随想录的题解。
要灵活啊，谁说买卖多次就必须要有循环了，只有最多买卖K次，需要再套一层循环，前面也做了无限次买卖的题了，不也只有外面一层循环？
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
if n == 0:
return 0
dp = [[0] * 4 for _ in range(n)]
dp[0][0] = -prices[0] #持股票
for i in range(1, n):
dp[i][0] = max(dp[i-1][0], max(dp[i-1][3], dp[i-1][1]) - prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][3])
dp[i][2] = dp[i-1][0] + prices[i]
dp[i][3] = dp[i-1][2]
return max(dp[n-1][3], dp[n-1][1], dp[n-1][2])
过。
四道买卖股票题目总结。
在卖股票的时候，把手续费减去就好了，注意初始化那里，第0天不持有股票依然返回0，不买不卖，而不是一个负数，因为求的是最大值。
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
length = len(prices)
if len == 0 or len(prices)==1:
return 0
dp = [[0] * 2 for _ in range(length)]
dp[0][0] = -prices[0]
dp[0][1] = 0
for i in range(1,length):
dp[i][0] = max(dp[i-1][1]-prices[i],dp[i-1][0])
dp[i][1] = max(dp[i-1][0]+prices[i]-fee,dp[i-1][1])
return dp[length-1][1]
这道题要掌握的方法，还有一个贪心法，动态规划方法没什么新意，但是不知道为什么，这道题贪心法的解答博客，竟然没有在话题目录里。
贪心法还要理解一下，时间原因没细看。
动态规划：
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
n = len(prices)
dp = [[0] * 2 for _ in range(n)]
dp[0][0] = -prices[0] #持股票
for i in range(1, n):
dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i] - fee)
return max(dp[-1][0], dp[-1][1])
贪心法：
class Solution: # 贪心思路
def maxProfit(self, prices: List[int], fee: int) -> int:
result = 0
minPrice = prices[0]
for i in range(1, len(prices)):
if prices[i] < minPrice: # 此时有更低的价格，可以买入
minPrice = prices[i]
elif prices[i] > (minPrice + fee): # 此时有利润，同时假买入高价的股票，看看是否继续盈利
result += prices[i] - (minPrice + fee)
minPrice = prices[i] - fee
else: # minPrice<= prices[i] <= minPrice + fee， 价格处于minPrice和minPrice+fee之间，不做操作
continue
return result
过