基础知识铺垫
重新回顾分治法的主要思想：
- divide:将大的问题分解为若干较小的问题
- conquer:继续分解子问题，直到base case,直接求解
- combine：层层合并子问题的解，直到得到原始大问题的解
对问题进行分析：
- 当子问题不关联、不重叠的时候，分治是一种较好的求解方法
- 当子问题重叠的时候，分治会造成计算资源的浪费
- 动态规划中每个子问题的求解只依赖于更小规模子问题的求解，由底向上
- 由此引发了最优化的问题：在一定条件下，寻找使得目标最优的解
- 本质：是一种以空间换时间的方式；递归+重叠子问题+最优子结构=动态规划问题
卡尔的关于动态规划的讲解步骤：
- dp数组以及下相应的下标
- 递推公式
- dp数组如何进行初始化（比较讲究）
- 遍历顺序的重要性（从前到后以及从后到前）
- 打印dp数组（打印出来看是不是按照上面的逻辑来的）
三个主要的特征：
- 重叠子问题（因为核心是穷举，在穷尽的过程中就会出现重叠子问题的情况；用的原因：否则无法避开重复计算来提高计算效率）
- 最优子结构（一般形式是用来求解最值的问题，局部最优解可以决定或者逼近全局最优解；用的原因：否则无法设计递归求解）
- 状态转移方程
吴师兄+自己总结的思路（联系分治法的思路）：
- 将原问题（一个大的问题）分解为若干规模较小的问题
- 同时保存子问题的答案，使得每个问题只求解一次
- 最终获得原问题的答案
三个步骤：
- 确定dp数组的含义，dp里面包含了所有的子问题，dp[i]是一个解
- 寻找dp数组元素之间的联系，推导出dp[i]怎么来
- 确定dp数组的初始状态
这里也给自己自己整理了一个模板出来了：（参考东哥的题解）
# 初始化状态
dp[0][0][...]=base case
# 进行状态转移
for 状态一 in 状态1的所有值
for 状态二 in 状态2的所有值
for ...
dp[状态一][状态二][...] =求最值(选择1，选择2，选择3)
主要的几种题目类型：
- 背包问题
- 打家劫舍问题
- 股票问题
- 子序列问题
背包问题：
主要有以下的几个类型：
- 0-1背包问题 （**）
- 完全背包问题（**）
- 多重背包问题：每个物品的选择是有限制的
- 混合背包问题
- 二维费用的背包问题
- 分组背包问题
- 背包问题求方案数
- 求背包问题的方案
- 有依赖的背包问题
目前自己就是完全掌握这两种情况就够了，其他的也没有时间再整理了，主要是要弄懂相应的物理模型。然后不同的题型可以套上去，这两种情况的逻辑要十分清晰，包括边界条件和状态转移方程，自己也要写一篇题解，出来，算是对自己所学的知识的一个巩固，不能流于表面，当成自己的模板来用才是硬道理。0-1背包问题和完全背包问题确实是最常见的背包问题，而且里面的思想本质上也是十分的灵活的，其实是很难掌握的一种类型，可能还是因为题目做的还是不够多的原因，有些题目其实根本看不出来就是背包问题的变形。
参考链接：https://www.bilibili.com/video/BV1K4411X766
0-1背包问题（最基础的概念要牢牢掌握）
一件物品要么选要么不选
看到B站上有一个讲的虽然简单，但是把底层的一些原理算是讲清楚了。
- 当前物品是否能够装入背包：物品的体积小于等于背包容量才能够装进去
- 能够装下的情况：不装当前物品，还有就是装当前物品
- 不装的话，就是选前面的物品，前n个物品的最佳组合和前n-1个物品的最佳组合是一样的
- 装的话，在预留装这个物品的空间的情况之下，前n-1个物品的最佳组合+当前物品的价值就是总的价值
- 在这两种情况中选取最大的一种情况：为当前最佳组合的价值
- 如果装不下当前的物品：前n个物品的最佳组合和前n-1个物品的最佳组合是一样的
问题进阶：在使得背包内总价值最大的情况下，背包内装了哪些物品(这里是一个理解的过程：找到到底是装了哪些编号的物品，使得背包的总价值最大！！！)
归纳：从表的右下角开始回溯（从后往前看），如果发现前n个物品最佳组合的价值和前n-1个物品最佳组合的价值是一眼的，说明第n个物品没有被装入，否则，第n个物品被装入。
这里举了一个例子，以右下角为例：
- 当前的是前4个物品，所能装的物品的最大价值为10
- 现在看第4个物品有没有被装入，如果没有被装入的话，那么它应该和前3个物品背包所能装的最大价值一致
- 但是我们通过表格发现1个是9，一个是10，说明4号物品被装进了背包
- 既然4号物品被装进了背包，空间由8变为3去装其他物品，现在问题转化为考虑前三个物品且背包容量为3的情况下所能够装的最大价值
- 3号物品到底有没有被装进去，如果3号没有被装入，也即考虑前3个物品和考虑前2个物品的是一样的，看表发现确实是一样的，说明3号物品确实没有被装入进去。依次类推，2号物品被装入，1号物品没有装入。
dp[i][j]:表示前i个物品，背包重量为j的情况下能够装的最大价值，其中并不是表示要将i个物品全部装入，而是i个物品满足装入背包条件下的最大价值。
dp[i][j] = max(dp[i-1][j] ,dp[i-1][j-w[i]] +v[i])
# 物品的重量
W=[2,3,4,5]
# 物品的价值
V=[3,4,5,6]
# 物品编号和背包容量
m,n=4,8
# 创建dp数组
dp=[[0]*(n+1) for _ in range(m+1)]
# 注意边界条件，创建数组的时候处理过了
#print(dp)
for i in range(1,m+1):
for j in range(1,n+1):
# 如果发现背包的容量小于当前物品的重量
# 和放入i-1个物品的情况相同
if j <W[i-1]:
dp[i][j]=dp[i-1][j]
#print(dp[i][j])
else:
dp[i][j]=max(dp[i-1][j],dp[i-1][j-W[i-1]]+V[i-1])
#print(dp[i][j])
#print(dp)
print(dp[m][n])
完全背包问题：每件物品可以选无限次（只要背包容量够）
一个容量为m的背包，现在有n种物品，每种物品有无限多件，他们的重量分别为Wi(1<=i<=n),他们的价值为Vi(1<=i<=n),求能放入背包的最大价值？
最大价值是物品数量i和背包容量j的函数，f[i][j]表示考虑前i件物品放入容量为j的背包下的最大价值，最终的最大价值就是物品数量i从0n,背包容量j从0m时的f[m][n]
当前背包容量为j我们要考虑第i件物品能否放入？是否一定要放入？
- 不能放入:f[i][j]=f[i-1][j]
- 能放入，但是要比较代价
- 若第i件不放入背包：f[i][j]=f[i-1][j]
- 第i件物品放入背包：f[i][j]=f[i][j-W[i]]+V[i]
对于前i件物品，背包容量为j-W[i]时可能已经放入了第i件物品，容量为j时还可以再放入第i件物品，用f[i][j-W[i]]更新f[i][j]
即要是从上一行同列的单元格直接复制过来的(不放入第件物品)，要么从同行单元格某一列的单元格+W[i]
得出相应的状态转移方程：
f[i][j] = f[i-1][j] （j<W[i]）
f[i][j] = max(f[i-1][j] , f[i][j-W[i]]+V[i]) （j>=W[i]）
同样的例子，这里的完全背包的话：
在表中带颜色的区域，表示此时的背包是可以容纳第i件物品，我可以选或者不选第i件物品
以前2个物品，容量为5的这个例子来理解，当前是能够被装入的：
- 如果不让第i个物品装入，那么最大价值就是上面过来的6
- 如果让第i个物品装入，那么将空间由5–>2此时，此时看前i物品（第i件物品仍然可以再次被选中），在背包容量为2的情况下的最大价值，通过查表我们我们可以看到此时最大价值为3，加上装入的4，总共的最大价值为4+3=7
# 附上相应的代码进行理解
# 物品的重量
W=[2,3,4,5]
# 物品的价值
V=[3,4,5,6]
# 物品编号和背包容量
m,n=4,8
# 创建dp数组
dp=[[0]*(n+1) for _ in range(m+1)]
# 注意边界条件，创建数组的时候处理过了
#print(dp)
for i in range(1,m+1):
for j in range(1,n+1):
# 如果发现背包的容量小于当前物品的重量
# 和放入i-1个物品的情况相同
if j <W[i-1]:
dp[i][j]=dp[i-1][j]
#print(dp[i][j])
else:
dp[i][j]=max(dp[i-1][j],dp[i][j-W[i-1]]+V[i-1])
#print(dp[i][j])
# print(dp)
print(dp[m][n])
以下是主要的一些题目：
- leetcoad509-斐波那契数列
- leetcoad322-零钱兑换的问题
- leetcoad518-零钱兑换II
- leetcoad53-最大子数组和
- leetcoad64-最小路径和
- leetcoad72-编辑距离
- leetcoad494-目标和
- 买卖股票系类问题（其实这个系列的问题挺难想到的）
- leetcode121-买卖股票的最佳时期
- leetcode122-买卖股票的最佳时期II
- leetcode123-买卖股票的最佳时期III
- leetcode309-最佳买卖股票时机含冷冻期（含有交易冷冻期）
- leetcod714-买卖股票的最佳时期含手续费（每次交易含手续费）
leetcoad509-斐波那契数列(easy)
题目回顾：斐波那契数列的是这样一个数列：1、1、2、3、5、8、13、21、34….，即第一项 f(1) = 1,第二项 f(2) = 1…..,第 n 项目为 f(n) = f(n-1) + f(n-2)。求第 n 项的值是多少？
这道题也是非常的经典，有助于自己理解很多的问题，从这道题上面挖掘出一些有用的东西出来才是关键的地方。分采用了三种方法（包含优化的过程）：
- 暴力递归法
- 带备忘录递归写法
- 动态规划的迭代写法（存储所有的状态）
- 优化动态规划的写法（只储存前两个状态进行滚动）
暴力递归法
class Solution:
def Fibonacci(self , n: int) -> int:
if n ==1 or n ==2:
return 1
else:
# 围绕这个数学表达式的形式
return self.Fibonacci(n -1) + self.Fibonacci(n - 2)
参考链接：https://leetcode-cn.com/problems/fibonacci-number/solution/dong-tai-gui-hua-tao-lu-xiang-jie-by-labuladong/
解法的弊端：
时间复杂度：子问题个数x解决子问题需要的时间=O(2^n) xO(1) =O(2^n)
低效的原因：存在太多重复计算的问题
采用带备忘录的递归写法（记忆化备忘录）
采用带备忘录的递归写法(至顶向下)：
每次遇到一个子问题先去「备忘录」里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了。一般使用一个数组充当这个「备忘录」，当然你也可以使用哈希表（字典），思想都是一样的。
# 时间复杂度大大降低
class Solution:
def fib(self, n: int) -> int:
memo = [0]*(n+1)
return Solution.helper(memo, n)
# 进行带备忘录的递归
# 把一颗存在巨量冗余的递归树通过剪枝，改造成一幅不存在冗余的递归树，极大的减少子问题（递归图中节点）的个数
def helper(memo:list, n:int):
if not n:
return 0
if n ==1 or n ==2:
return 1
if memo[n] != 0:
return memo[n]
memo[n] = Solution.helper(memo, n - 1) + Solution.helper(memo, n - 2)
return memo[n]
dp数组的迭代写法
状态转移方程是解决问题的核心，状态转移方程是直接代表着暴力解法的，只要能够写出暴力解法，优化方法就是用备忘录或者DPtable来解决的。
把备忘录独立出来一张表
这个dp表像之前剪枝的结果，但是是反过来的，本质上差不多，所以在效率上也就差不多。
class Solution:
def fib(self, n: int) -> int:
dp =[0]*(n+1)
# 这里需要加入if elif语句表明递归的出口
#if not n:
if n==0:
return 0
#第2个判断语句也可以用if来写，只要不与上一个发生冲突就行
# if n in [1,2]:
# return 1
elif n<=2:
return 1
dp[1]=dp[2]=1
for i in range(3,n+1):
# 围绕这个数学表达式的形式
dp[i]=dp[i-1]+dp[i-2]
return dp[n]
优化dp动态规划
状态压缩，每次状态转移只需要DP table中的一部分，只记录必要的数据，当前状态只和之前的两个状态有关，不需要dp表来存储所有的状态，想办法只存储之前的两个状态（把DP table的大小从n缩小到2），将空间复杂度从O(N)降低到O(1)
class Solution:
def Fibonacci(self , n: int) -> int:
if n ==1 or n ==2:
return 1
prev,curr = 1,1
for i in range(3,n+1):
# 记录前两个状态的和
sum = prev + curr
#不断的向前滚动这两个状态
prev = curr
curr = sum
return curr
附上另一个大佬的版本(运用了python的语法)：
class Solution:
def Fibonacci(self, n):
# 这里的f就是类似于一个dp表格，用来记录加和的值，值得最后的一个值就是最终的结果
f = [0,1,1]
i=3;
while(i<=n):
f.append(f[i-1]+f[i-2])
i = i + 1
return f[n]
leetcoad322-零钱兑换的问题(middle)
把题目在好好的梳理一遍：给你一个整数数组coins，表示不同面额的硬币，以及一个整数amount,表示总金额，计算并返回可以凑成总金额所需的最少的硬币的个数，如果没有任何一种硬币的组合能组成总金额，返回-1，你可以认为每一种硬币的数量是无限的。
看评论区的方法：方法很多，有背包(动态规划)、深度遍历（dfs）、广度遍历（bfs）、暴力递归的方式
这个问题是动态规划问题，因为它具有「最优子结构」的。要符合「最优子结构」，子问题间必须互相独立。
思考如何列出正确的状态转移方程：
- 确定base case:
- 确定状态：原问题和子问题中会变化的变量，只有目标金额会不断的向base靠近，唯一的状态就是目标金额
- 确定选择：导致状态产生变化的行为，目标金额在变是因为在选择硬币，每选择一次硬币，就减少了目标金额
- 明确dp函数/数组的定义：输入一个目标金额n,返回凑出目标金额n的最少硬币数量
如果是采用暴力的方式：这种写法是超时的，也是需要消除重叠子问题的问题
时间复杂度分析：子问题总数 x每个子问题的时间=O(n^k)[递归树的结点总数] xO(k)[每个子问题都含有一个for循环]=O(k*n^k)[指数级别的]
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
def dp(n):
# 确定边界条条件
#目标金额为0，需要0,目标金额为负的时候，返回-1
if n == 0:
return 0
if n < 0:
return -1
# 求最小值，所以初始化为正无穷
res = float('INF')
for coin in coins:
subproblem = dp(n - coin)
# 子问题无解，跳过
if subproblem == -1:
continue
res = min(res, 1 + subproblem)
return res if res != float('INF') else -1
return dp(amount)
#下面的5行代码可以通过简化的上面的2行代码来写
# if res != float('INF') :
# return res
# else:
# return -1
# return dp(amount)
带备忘录的递归（至顶向下相除重叠问题）
子问题总数：小于n，是O(n)级别的
处理一个子问题的时间：O(k)
总的时间复杂度：O(nk)
现在就要通过备忘录的方式消除一部分重叠子问题（代码不一定是最好的模板，但是分析的思路是很好的，值得学习）：
class Solution:
def minMoney(self , arr: List[int], aim: int) -> int:
#备忘录
memo = dict()
def dp(n):
#查备忘录避免重复计算
if n in memo:
return memo[n]
# 确定边界条条件
if n == 0:
return 0
if n < 0:
return -1
# 求最小值，所以初始化为正无穷
res = float('INF')
for coin in arr:
subproblem = dp(n - coin)
# 子问题无解，跳过
if subproblem == -1:
continue
res = min(res, 1 + subproblem)
#记入备忘录
memo[n] = res if res != float('INF') else -1
return memo[n]
return dp(aim)
通过dp数组的迭代写法（至底向上相除重叠问题）
略（采用吴师兄的写法比较好理解）
总结：只要通过状态转移方程写出暴力递归写法，剩下的就是优化递归树，消除重叠子问题
解决问题：穷举，穷举所有的可能性，算法设计就是先思考“如何穷举”，然后再追求如何聪明的穷举
列出动态转移方程就是解决“如何穷举的问题”
归纳出相应的状态转移方程：
难点：
- 穷举需要递归实现
- 有的问题本身的解空间复杂，不那么容易穷举完整
- 备忘录和dp table就是在追求“如何聪明穷举”，用空间换时间的思路，以此来降低时间复杂度
采用吴师兄的解法思路如下（保姆式）：
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
# 初始化数组 dp，长度为 amount + 1，因为在 dp 数组中还会存储金额为 0 的情况
# 首先将数组 dp 里面的值都初始化为 -1（一种做题的方式，比如上面用的是正无穷）
# -1 表示当前的金额还没有找到需要的最少硬币个数
# dp[i]的含义：当目标金额为i时，至少需要dp[i]枚硬币凑出
dp = [-1]*(amount +1)
# 想要凑齐 0 元的最少硬币个数是 0 个
dp[0]=0
# 依次计算想要凑齐 1 元到 amount 的最少硬币个数是多少
for i in range(1,amount+1):
# 对于每个金额 i 来说，coins 中的每个面值小于 i 的硬币都可以尝试去拼凑 i
# 比如 i = 8 ，coins 为 [1,2,5,7,10]
# 其中 1，2，5，7 都小于 8
# 1 可以尝试去拼凑 8
# 2 可以尝试去拼凑 8
# 5 可以尝试去拼凑 8
# 7 可以尝试去拼凑 8
# 所以，设置一个变量 j ，遍历数组 coins
for j in range(len(coins)):
# 1、如果当前的硬币面值 coins[j] 小于了 i，表示这枚硬币有可能可以拼凑到 i
# 2、那么 i - coins[j] 表示面值 coins[j] 的硬币想要拼凑 i 需要那些面值的硬币金额
# 3、而 dp[i-coins[j]] 表示想要凑齐 i - coins[j] 元需要的最少硬币个数
# 4、如果 dp[i-coins[j]] != -1 ，表示想要凑齐 i - coins[j] 元需要的最少硬币个数有结果
#if dp[i-coins[j]] != -1 and coins[j] <=i:这里的这种写法是存在问题的，只有在coin[j] <=i满足的情况下才会去判断dp[i-coins[j]]!=-1的情况，不能够颠倒
if coins[j] <=i and dp[i-coins[j]] != -1 :
# 这个时候，对于金额 i 来说
# 1、如果它之前还没有找到凑齐 i 元需要的最少硬币个数
# 2、如果此时计算的最少硬币个数比之前保存的结果 dp[i] 更小
# 那么更新 dp[i]
if dp[i]==-1 or dp[i] >dp[i-coins[j]] +1:
# 更新 dp[i]
# dp[i] 表示想要凑齐 i 元需要的最少硬币个数
# 这个时候 dp[i] 为获取面值为 j 的那 1 个硬币
# 加上获取面值为 i - coins[j] 最少需要 dp[i - coins[j]] 个硬币
dp[i] = dp[i-coins[j]] +1
# dp[amount] 表示想要凑齐 amount 元需要的最少硬币个数
# 返回这个结果就行
return dp[amount]
精简版(其实最后写出来就只有几行代码，难的是里面的思想)：
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [-1]*(amount +1)
dp[0]=0
for i in range(1,amount+1):
for j in range(len(coins)):
if coins[j] <=i and dp[i-coins[j]] != -1 :
if dp[i]==-1 or dp[i] >dp[i-coins[j]] +1:
dp[i] = dp[i-coins[j]] +1
return dp[amount]
后面自己又做了一遍，发现这个问题在当时只是熟悉了一下做题的套路，等再次来看这道题的时候，还是很懵，所以没办法就只能死磕，把这个问题给整理清楚，发现每次写的还都不一样，也许就是这些题目比较经典的原因，需要反反复复的去做，才能体会里面的一些精髓所在:
以下为自己后来又实现代码的过程，同时自己也实地的用excel做了一份用于自己的理解的过程：
以其中的一个值为例子来理解这个表，dp[1][4]这个位置，表示此时的硬币值为1，金额为4，可以进行找零过程（我用箭头标注的这个过程就是十分标准的完全背包的过程）
- 如果不选第i枚硬币的话，dp[0][4]=12，
- 在选第i枚硬币的情况下dp[1][4]=dp[1][4-1]+1=dp[1][3]+1=4,取两种情况下的最小值4为此时的最小硬币的数量。
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
n=len(coins)
# 构建dp数组，dp[i][j]表示选择前i种硬币能凑齐j元需要的最少的硬币的数量
# 这里一定是有硬币的，所以在构建dp数组的时候需要注意,初始化为一个较大的值+inf或者是amount+1
dp=[[amount+1]*(amount+1) for _ in range(n+1)]
# 设置初始条件：需要找零的金额为0的时候，所需要的硬币是为0的
dp[0][0]=0
# 第一层循环遍历硬币
for i in range(1,n+1):
# 第二层循环遍历背包
for j in range(amount+1):
# 采用完全背包的思路
# 如果当前的硬币面值大于要凑成的金额，没有办法参与找零（容量有限，无法选择第i种硬币），直接copy值下来
if j<coins[i-1]:
dp[i][j]=dp[i-1][j]
# 当当前的硬币值小于要凑成的金额的时候，这个时候才是可以参与找零的过程
else:
# 有两种选择的方案（十分标准的完全背包的套路问题）
# 一种是选用该硬币，看看硬币能否凑成amount-nums[i],dp[i][j]=dp[i][j-coins[i-1]]+1
# 第二种是，不选用该硬币，直接用前面的硬币来组成：dp[i][j]=p[i-1][j]
# 取两种结果的最小值作为
dp[i][j]=min(dp[i-1][j],dp[i][j-coins[i-1]]+1)
res=dp[n][amount]
# 还用进行最后的判断，对于没有任何一种硬币能够组成的情况，直接返回-1，也就是之前自己设置的amount+1的情况
if res!=amount+1:
return res
else:
return -1
leetcoad518-零钱兑换II(middle)
先对题目进行解析：给一个整数数组coins表示不同面额的硬币，另给一个整数amount表示总金额，计算并返回可以凑成总金额的硬币组合数，如果任何的硬币组合数都无法凑出总金额，返回0，假设每一种面额的硬币有无限个，数据结果符合32位带符合整数。
与上一题的区别：计算凑成总金额的最小硬币的数量
本题：凑成硬币的组合数的情况
对于第0行和第0列的情况来分析，没有硬币的时候无法找零，所以所有的第0行的的组合数为0，第0列表示，在需要找零为0的情况的硬币的组合情况，如果要用到当前的硬币作为组合的话，它的起始条件就是1（这有点不是特别的好想），真正难的还是它的状态转移方程，和纯完全背包又不太一样，强调的是组合数
用下面的这张图来辅助理解完全背包的问题，可以说再次回顾的时候还是发现了很多的细节的，也加深对这道题的理解，透过这道题进行相应的发散才是最关键的问题。
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
n=len(coins)
# 构建dp数组并明确dp数组的函数，选用前i个种类的硬币在凑齐金额为j的情况下的组合数
dp=[[0]*(amount+1) for _ in range(n+1)]
# 把第0列的情况更改为1,表示直接不需要任何面值，可以把情况记录为1
for j in range(1,n+1):
dp[j][0]=1
# 采用完全背包的思路来解题
for i in range(1,n+1):
for j in range(1,amount+1):
# 如果发现当前的硬币值大虚需要找零的金额的时候，无法进行找零，组合数为上一行复制过来的
if coins[i-1] >j:
dp[i][j]=dp[i-1][j]
# 如果发现能够进行相应的找零，需要分两种情况
else:
# 情况一：不选用第i枚硬币，此时dp[i][j]=dp[i-1][j]
# 请款二：选用第i枚硬币的情况,此时dp[i][j]=dp[i][j-coins[i]]
dp[i][j]=dp[i-1][j]+dp[i][j-coins[i-1]]
return dp[n][amount]
leetcoad53-最大子数组和
弄清楚连续子数组的定义
弄清楚dp[i]的含义：表示以第i个元素结尾的最大子数组的和（肯定是以第i个元素进行结尾，但是不一定包括前面所有的数）
最后返回dp数组中最大的那个数
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
# 因为后面会使用到 nums 的长度
# 所以先进行判空操作
# 如果数组 nums 为空，返回 0
if not nums:
#if len(nums)==0:
#if nums is None:
return 0
# 获取数组的长度
n = len(nums)
# 设置一个数组 dp，长度和数组 nums 长度一致
# dp[0] 表示以第 0 个元素结尾的最大子数组的和
# dp[1] 表示以第 1 个元素结尾的最大子数组的和
# dp[i] 表示以第 i 个元素结尾的最大子数组的和
dp =[0]*n
#dp =[0 for _ in range(n)]
# dp[0] 表示以第 0 个元素结尾的最大子数组的和
# 初始化 dp[0]
dp[0]=nums[0]
# 变量 maxNum 表示数组 dp 中最大的那个值
# 即 maxNum 表示最大的连续字段和
maxNum=dp[0]
# 从 1 开始遍历数组 nums
for i in range(1,n):
# 在遍历的过程中，去获取以第 i 个元素结尾的最大子数组的和
# 如果以 nums[i-1]结尾的最大字段和为正数
# 那么以第 i 个元素结尾的最大子数组的和就是自己本身加上以 nums[i-1]结尾的最大字段和
if dp[i-1]>0:
# dp[i-1] 是正数
# 所以 dp[i] 的值为 nums[i] 加上 dp[i-1]
# 因为 正数 + 变量 > 变量
# dp[i -1] + nums[i] > nums[i]
dp[i]=dp[i-1]+nums[i]
# 否则 dp[i-1] 不是正数，为负数或者 0
else:
# 那么 dp[i] 的值为 nums[i]
# 因为 负数 + 变量 < 变量
# dp[i -1] + nums[i] < nums[i]
dp[i]=nums[i]
# 在更新 dp[i] 的过程中，更新 maxNum 的值
# 如果此时 dp[i] 的值大于了 maxNum
if dp[i]>maxNum:
# 那么 maxNum 更新为 dp[i]
maxNum=dp[i]
# 最后返回 maxNum
return maxNum
leetcoad64-最小路径和(middle)
解题的关键：
对于不在第一行和第一列的元素，可以从其上方相邻元素向下移动一步到达，或者从其左方相邻元素向右移动一步到达，元素对应的最小路径和等于其上方相邻元素与其左方相邻元素两者对应的最小路径和中的最小值加上当前元素的值。由于每个元素对应的最小路径和与其相邻元素对应的最小路径和有关，因此可以使用动态规划求解。
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
# m 表示有多少行
m= len(grid)
# n 表示有多少列
n = len(grid[0])
dp=[[0]*n for _ in range(m)]
#dp=[[0 for _ in range(n)] for _ in range(m)]
dp[0][0]=grid[0][0]
# i 从 1 遍历到 n - 1
for i in range(1,n):
dp[0][i]=dp[0][i-1]+grid[0][i]
# j 从 1 遍历到 m - 1
for j in range(1,m):
dp[j][0]=dp[j-1][0] +grid[j][0]
# 接下来从第 1 行到第 m - 1 行
# 从第 1 列到底 n - 1 列
for i in range(1,m):
for j in range(1,n):
dp[i][j]=min(dp[i-1][j],dp[i][j-1]) +grid[i][j]
# dp[m-1][n-1] 表示第 m - 1 行第 n - 1 列的最优解
return dp[m-1][n-1]
leetcoad72-编辑距离
刚拿到这个题目的时候肯定是特别的难想的：尽管题目也已经说了一些相应的操作，但是代码如何实现确实是一个问题（可以说是根本想不到的方式），而且代码的逻辑根本也不是像题目中描述的那样的，所以第一次做的时候肯定也是一头雾水。需要想到动态规划的思路，这才是问题的本源
还有如果一旦遇到一个新的题目，如何从一个一维dp切换到一个二维的dp也是问题的关键（这里就是一个很关键的思考流程在里面）
这道题总的来说还是比较难的，这里应该要花一点时间好好整理一下，而且最好方法尽量的多元化一点
暴力解法
在看labuladong的时候一些比较好的地方
这张动图很好的展示了这样的一个过程，关键在于如何正确做出选择，根据这张动图就可以配合后面的代码来加深对递归代码的理解。
这里用两个指针分别指向字符串的最后，然后一步步的往前走，缩小问题的规模，根据上面的步骤，出现了四种操作：
- 遍历到的时候，两者本来就是相等的，不对其进行操作，直接往前移动i,j就行了
- j走完了s2的时候，结果i没有走完s1，用删除的操作，将s1缩短为s2就可以
- i走完了s1的时候，结果j没有走完s2，用插入操作把s2剩下的字符全部插入s1中
- 然后就是不好处理的递归的代码部分
递归的出口：上面已经写清楚了
递归的代码部分：
理解函数的部分：dp(i,j) :该函数的返回值就是s1[0…i]和s1[0…j]的最小编辑距离
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
# 定义dp函数(只是一个代号)
# dp(i,j) :该函数的返回值就是s1[0...i]和s1[0...j]的最小编辑距离
def dp(i,j):
# 定义递归的出口
# 当s1或s2走完了，直接返回另一个字符串剩下的长度
if i==-1: return j+1
if j==-1: return i+1
if s1[i]==s2[j]:
# 什么都可以不用做
# s1[0..i]和s2[0...j]的编辑距离与s1[0..i-1]和s2[0...j-1]的编辑距离相同
return dp(i,j)=dp(i-1,j-1)
# s1[i]!=s2[j]的情况的时候
else:
# 返回的分别是替换 删除与插入的操作
return min(dp(i-1,j-1),dp(i-1,j),dp(i,j-1))+1
# i,j初始化指向最后一个索引
return dp(len(s1)-1,len(s2)-1)
动态规划的解法
其实也是对暴力的解法做了一定的优化
参考吴师兄的解题思路，做了如下的一些整理的过程
总共有三种方案：
- 将word1中前L1-1个数字改为word2中的前L2-1个数字，再把a—->b
- 将word1中的前L1-1个数字改为word2，再删除a
- 将word1中的前L1个字符修改为word2前L2-1个字符，再向word1中插入一个字符b
- 选出其中的较小值，再判断是否需要执行一次插入操作、或者一次删除操作、或者一次替换操作
为了进一步更好的弄清楚相应的解题过程，这里自己用表格来详细的模拟了这样的一个过程
- 初始化表格，行数为s1中的长度，列数为s2中的长度，同时对于0的时候，预定的是空字符串的时候（对于索引为0的时候这里理解为空字符串确实是有点费解）
- 在对边界条件的处理上后面的代码中都会有详细的注释，特别是对于dp[0][j]和dp[i][0]的填充，本质上也是一种很好的初始化的过程，只有在脑海里面已经有了一个很明晰的二维表格的时候才能算是真正的看懂了
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
# 获取两个字符串的长度
L1,L2=len(word1),len(word2)
# 二维数组dp[i][j]表示word1的前i个字符转化为word2中的前j个字符所需要的最少的操作
# dp[0][0]:word1的前0个字符转化为word2的前0个字符需要的最少操作（说人话就是空字符串变成空字符串需要的最少的一个操作）
# dp[L1][L2]表示word1中的前L1个字符转化为word2中的前L2个字符所需要的最少的操作
dp=[[0]*(L2+1) for _ in range(L1+1)]
# print(dp)
# dp[i][0]表示:把word1中的前i个字符转化为word2中的前0个字符需要的最少的操作(也即把word1中的前i个字符全部都删除,变成空字符串需要的操作数)
# 只需要每次对word1中的字符执行删除操作,就可以将word1中的字符全部删除
for i in range(L1+1):
dp[i][0]=i
# dp[0][j]表示:将word1中的前0个字符转化为word2中的前j个字符所需要的最少的操作次数(空字符串经过多少次变化变成word2中的前j个字符)
for j in range(L2+1):
dp[0][j]=j
# print(dp)
# 通过两个for循环来设置二维数组中所有元素的值
for i in range(1,L1+1):
for j in range(1,L2+1):
# 如果发现word1[i-1]==word2[j-1] 即当word1中的前i-1个字符成功转化为word2中的前j-1个字符后
# 自然而然word1中的前i个字符也成功的转化为word2中的前j个字符(因为两个字符串下一个字符是相等的不需要转换操作)
if word1[i-1]==word2[j-1]:
dp[i][j]=dp[i-1][j-1]
# 当当前遍历的元素不相等的时候,意味着在dp[i-1][j-1]的基础上上还要转换当前的元素
else:
# 此时的dp[i][j]可以从三种状态中转换过来
# 状态一:dp[i-1][j-1]--->dp[i][j] 当前遍历的字符.两个都不相等(a--->b)
# 状态二:dp[i-1][j]--->dp[i][j],word1中的前i-1个字符已经转换成为了word2中的前j个字符(直接删除word1中当前遍历的元素)
# 状态三:dp[i][j-1]--->dp[i][j],word1中当前的前i个字符已经转换了word2中的前j-1个字符(在word1中插入word2中当前遍历的字符)
# 取三者状态中最小值,作为最终的dp[i][j]的值
dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1
# 将最后的结果返回
return dp[L1][L2]
leetcoad494-目标和
做题分析：
要与分割等和子集的题目进行比较分析：那一题只是要返回是否可以进行进行相应的分割，我们在定义dp数组的时候的需要记录到底是True还是False目标和这道题：不仅要找出能够满足目标和要求的，还要求返回返回方法数，dp数组中需要记录的就是具体的方法数
如何把该问题合理的转化为0-1背包问题才是问题的关键和要点
定义状态：根据背包问题的经验，将dp[i][j]定义为从数组nums中0~i的元素进行加减可以得到j的方法的数量或者换一种解释的方式：我们要做的就是从数组nums中选出若干数字（每个元素最多选择一次），使其和刚好等于target,并计算有多少种不同的选择方式。
这里再重新回顾一下0-1背包问题的原型：有w个物品，有容量N的背包，其中每件物品都有一定的容量以及相应的价值，问背包中能够装入的最大的价值
难点：根据状态去考虑如何利用子问题的转移从而得到整体的解，问题的关键不是nums[i]的选与不选，而是nums[i]是+还是-，这就导致状态方程会有一定的变化dp[i][j]=dp[i-1][j-nums[i]]+dp[i-1][j+nums[i]]
其中nums[i]这个元素可以执行＋，也可以执行-，那么dp[i][j]的结果值就是+/-之后对应位置的和
以下的代码实际上参考了东哥的解法，本质上还是对该问题做了一个转化，转化成为了0-1背包问题，其实边界问题一直是细节。
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
# 参照东哥的解法
# 先求nums数组中的和
sum=0
for c in nums:
sum+=c
# print(sum)
# 当nums中所有非负的和都不能等于target或者sum+target是奇数的话也不可能找到对应的数
if sum <abs(target) or (sum+target)%2==1:
return 0
# 以下写一个函数，转化为0~1背包的问题，其中背包的容量为(sum+target)//2
# 注意这个问题已经被转化了，所以就不要盯着之前的问题来看
def subsets(nums,s):
# 以下就是0-1背包问题的模板了
n=len(nums)
# 构建dp[i][j]:表示在前i件物品中选择，能够正好凑齐s的一些选择
dp=[[0]*(s+1) for _ in range(n+1)]
# 当背包的容量的0的时候，此时需要把dp[i][j]的值全部置为1，表示：什么都不装也h是一种解法
for i in range(0,n+1):
dp[i][0]=1
# print(dp)
# n/c 0 1 2 3 4
# 0 1 0 0 0 0
# 1 1
# 1 1
# 1 1
# 1 1
# 1 1
# 初始化dp数组，因为要能够刚好凑齐
# 当s=0的时候，对应的值为0
# 选择i件物品放入背包和不选择第i件物品放入背包这个两种
for i in range(1,n+1):
for j in range(0,s+1):
# 当当前的背包容量小于此时的数值的时候，此时放入的物品由上一个状态决定
if nums[i-1]>j:
dp[i][j]=dp[i-1][j]
# 当前的背包容量大于当前的数值的时候就有两种选择
else:
dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i-1]]
return dp[n][s]
# 实际上就是用这个函数来求对应的返回的符合条件的数目
return subsets(nums,(sum+target)//2)
这题做完之后，把该题与分割等和子集的问题拆分起来一起看，有相通的地方，也有不同的地方。同原版的0-1背包问题对比也有一些差异。以下也是做一些相应的总结“
- 首先问题的转化就是一个难点：存在一定的公式推导，转化为装满容量为s的背包有几种方法：
- 特例的判断:如果目标值的绝对值大于s，是不存在方案的，如果是target>s还是-target>s，根据数学知识的一些常识吧。
- 为什么是0-1背包问题？nums中的数只用一次，但是又和0-1背包问题存在区别：之前的是容量为j的背包，最多能装多少，本题是装满有几种方法，是一个组合的问题
买卖股票系类问题
这一系列问题是值得自己去好好的吸收与整理，形成自己的知识系统，收纳不同的方法体系。
哪些因素决定了可以获得的最大收益
- 在哪些天进行了交易
- 进行了多少次交易
- 每天结束时持有的股票数（这个点容易忽略）
吴师兄总结的一套模板的解题方法
定义状态： - i表示天数
- K表示交易次数，每次交易包含买入和卖出（当成一个闭区间），这里只在买入的时候将k -1（关键点）
- 0表示当前持有0份股票
- 1表示当前持有1份股票
- dp i k 0/1 :第i天结束后，手上持有0/1份股票，此时最多进行了k次交易的情况下可以获得的最大收益
动态规划的步骤： - 置底向上，从前向后遍历，实现一个萝卜一个坑
- 对于每个坑（第i天）来说都有两种状态（这里的理解非常重要）：
- 今天不持有股票
- 状态一：第i-1天持有股票，第i天卖出，即昨天持有股票，今天卖出【卖出】
- 状态二：第i-1天不持有股票，第i天不操作，即昨天不持有股票，今天不操作【休息】
- 今天持有股票
- 状态一：第i-1天持有股票，第i天不操作，即昨天持有股票，今天不操作【休息】
- 状态二：第i-1天不持有股票，第i天买入，即昨天不持有股票，今天买入【买入】
- 今天不持有股票
leetcode121-买卖股票的最佳时期(easy)（限定交易次数k=1）
题目描述：给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例1：
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例2：
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
#单单论这道题，如果是用这样的一种方法，可能用时比较的长，但是也是有助于理解的。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# 先获取数组的长度
n = len(prices)
# 设置一个三维数组 dp
# dp[i][k][b]
# i 表示天数，dp[i] 表示第 i 天的最大利润
# k 表示最多交易次数，每次交易包含买入和卖出，这里只在买入的时候将 k - 1
# 注意：【 k 表示最多交易次数，而不是实际交易次数，比如最多交易两次可能实际只交易一次】
# b 表示当前是否持有股票，取值为 0 和 1
# 其中 0 表示当前持有 0 份股票，即【不持有】股票
# 而 1 表示当前持有 1 份股票，即【持有】股票
# 在本题中，k 的值为 1，i 的取值范围为数组 prices 的长度，从 0 开始
# 越在前面的维度，总体上是越出现在后面
# dp =[[[0]*2]*2]*n
dp = [[[0] *2 for _ in range(2)]for _ in range(n)]
# dp[0][0][0] 表示在第 0 天结束时，即收盘后，手上持有 0 份股票，且此时最多进行了 0 次交易的情况下可以获得的最大收益
# 此时，就是什么都没做，利润为 0
dp[0][0][0]=0
# dp[0][1][0] 表示在第 0 天结束时，即收盘后，手上持有 0 份股票，且此时最多进行了 1 次交易的情况下可以获得的最大收益
# 此时，就是什么都没做，利润为 0
dp[0][1][0]=0
# dp[0][1][1] 表示在第 0 天结束时，即收盘后，手上持有 1 份股票，且此时最多进行了 1 次交易的情况下可以获得的最大收益
# 手上持有了 1 份股票，那肯定是执行了买入操作，然后又还没有卖出，那么钱都投入了股票中，利润就是负的，即为 -prices[0]
# 相当于是贷款的形式
dp[0][1][1]=-prices[0]
# 动态规划：自底向上，即从前向后遍历，实现一个萝卜一个坑
# 这里i的范围是从1开始的，因为i=0的时候是没有前一个和状态的说法的，由后面的两种状态需要的值发现，需要三个初始值
for i in range(1,n):
# 对于每个坑来说，都有两种状态
# 今天也就是第 i 天
# 1、今天【不持有】股票
# 第 i - 1 天【持有】股票，第 i 天卖出
# 昨天【持有】股票，今天卖出
# vs
# 第 i - 1 天【不持有】股票，第 i 天不操作
# 昨天【不持有】股票，今天不操作
# dp[i][k][0]=max(dp[i-1][k][1]+prices[i],dp[i-1][k][0])
dp[i][1][0]=max(dp[i-1][1][1]+prices[i],dp[i-1][1][0])
# 2、今天【持有】股票
# 第 i - 1 天【持有】股票，第 i 天不操作
# 昨天【持有】股票，今天不操作
# vs
# 第 i - 1 天【不持有】股票，第 i 天买入
# 昨天【不持有】股票，今天买入
# dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i])
dp[i][1][1]=max(dp[i-1][1][1],dp[i-1][0][0]-prices[i])
# for 循环结束后，dp 数组填充完毕
# dp[length - 1][1][0]
# 表示第 length - 1 天结束时，即收盘后，手上持有 0 份股票，且此时最多进行了 1 次交易的情况下可以获得的最大收益
return dp[n-1][1][0]
尝试采用其他的方法：在做剑指offer的时候的一些解法（）
剑指offer和这题的区别的地方：这题的数组可以为空，offer上的那道题的数组一定是有值的，所以不能完全把代码直接复制过去
状态定义：设置动态dp，dp[i]表示代表以price[i]为结尾的子数组的最大利润（前i日的而最大利润）
转移方程：前i日的最大利润=前i-1的最大利润dp[i-1]和第i日卖出的最大利润中最大值
用方程来表示的话：dp[i]=max(dp[i−1],prices[i]−min(prices[0:i]))
初始状态：p[0]=0 ，即首日利润为 0
返回值：dp[n−1] ，其中 n 为 dp 列表长度。
# 这种写法相对来说非常的慢
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n=len(prices)
if not prices:
return 0
dp=[0]*n
# 初始状态
dp[0]=0
for i in range(1,n):
dp[i]=max(dp[i-1],prices[i]-min(prices[:i]))
return dp[n-1]
看了K神优化后的代码，这里也放在这里学习一下：
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n=len(prices)
# 将成本预先定义成无穷大
# 用profit变量代替了状态变量
cost, profit = float("+inf"), 0
for price in prices:
# cost总是存储之前cost和目前遍历的价格的最小值
cost = min(cost, price)
profit = max(profit, price - cost)
return profit
采用贪心算法的思路：
leetcode122-买卖股票的最佳时期II(middle)（限定交易次数k无限大）
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
#设置二维的dp数组
dp = [[0]*2 for _ in range(n)]
#dp[0][1]表示：在第0天结束的时候，手上持有1份股票
dp[0][1]=-prices[0]
#dp[0][0]表示：在第0天结束的时候，手上持有0份股票
dp[0][0]=0
for i in range(1,n):
#今天不持有股票的情况
# 第一种状态：第i-1天持有股票，在第i天卖出：dp[i][0]=dp[i-1][1]+prices[i]
# 第二种状态：第i-1天不持有股票，第i天休息:dp[i][0]= dp[i-1][0]
dp[i][0]= max(dp[i-1][1]+prices[i],dp[i-1][0])
#今天持有股票的情况
# 第一种状态：第i-1天持有股票，第i天不操作:dp[i][1]=dp[i-1][1]
# 第二种状态：第i-1天不持有股票，第i天进行买入操作:dp[i][1]=dp[i-1][0]-prices[i]
dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])
return dp[n-1][0]
尝试采用其他的解法：
相较于上一题，这里的k值为正无穷
leetcode123-买卖股票的最佳时期III(hard)（限定交易次数k=2）
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# 先获取数组的长度
n = len(prices)
# 设置一个三维数组 dp
# dp[i][k][b]
dp = [[[0]*2 for _ in range(3)] for _ in range(n)]
#设置几种初始状态
dp[0][2][1] = -prices[0]
dp[0][2][0] = 0
dp[0][1][0] = 0
dp[0][1][1] = -prices[0]
dp[0][0][0] = 0
# 动态规划：自底向上，即从前向后遍历，实现一个萝卜一个坑
for i in range(1,n):
# 对于每个坑来说，都有两种状态
# 今天也就是第 i 天
# 1、今天【不持有】股票，且此时最多进行了 2 次
# 第 i - 1 天【持有】股票，第 i 天卖出:dp[i][2][0]=dp[i-1][2][1]+prices[i]
# 第 i - 1 天【不持有】股票，第 i 天不操作:dp[i][2][0]= dp[i-1][2][0]
dp[i][2][0]=max(dp[i-1][2][1]+prices[i],dp[i-1][2][0])
# 2、今天【持有】股票，且此时最多进行了 2 次
# 第 i - 1 天【持有】股票，第 i 天不操作：dp[i][2][1]=dp[i-1][2][1]
# 第 i - 1 天【不持有】股票，第 i 天买入：dp[i][2][1]=dp[i-1][1][0]-prices[i]
dp[i][2][1]=max(dp[i-1][2][1],dp[i-1][1][0]-prices[i])
# 3、今天【不持有】股票，且此时最多进行了 1 次
# 第 i - 1 天【持有】股票，第 i 天卖出:dp[i][1][0]=dp[i-1][1][1]+prices[i]
# 第 i - 1 天【不持有】股票，第 i 天不操作:dp[i][1][0]=dp[i-1][1][0]
dp[i][1][0] = max(dp[i-1][1][1]+prices[i],dp[i-1][1][0])
# 4、今天【持有】股票，且此时最多进行了 1 次
# 第 i - 1 天【持有】股票，第 i 天不操作:dp[i][1][1]=dp[i-1][1][1]
# 第 i - 1 天【不持有】股票，第 i 天买入:dp[i][1][1]=dp[i-1][0][0]-prices[i]
dp[i][1][1] = max(dp[i-1][1][1],dp[i-1][0][0]-prices[i])
return dp[n-1][2][0]
leetcode188-买卖股票的最佳时期IV(hard)（限定交易次数最多为k）
这种情况相当于是股票问题的一个通用的版本（重点理解）。
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
#题目这里有一个陷阱：prices[i]的长度是有可能为0,此时数组为空，需要加一个判断语句
if not prices:
return 0
# 先获取数组的长度
n = len(prices)
# 设置一个三维数组 dp
# dp[i][k][b]
dp = [[[0]*2 for _ in range(k+1)] for _ in range(n)]
#用一个for循环来遍历可能的交易的次数
for j in range(1,k+1):
#设置几种初始状态
dp[0][j][1] = -prices[0]
dp[0][j][0] = 0
dp[0][j-1][0] = 0
# 动态规划：自底向上，即从前向后遍历，实现一个萝卜一个坑
for i in range(1,n):
# 对于每个坑来说，都有两种状态
# 今天也就是第 i 天
# 1、今天【不持有】股票，且此时最多进行了 j 次
# 第 i - 1 天【持有】股票，第 i 天卖出:dp[i][j][0]=dp[i-1][j][1]+prices[i]
# 第 i - 1 天【不持有】股票，第 i 天不操作:dp[i][j][0]= dp[i-1][j][0]
dp[i][j][0]=max(dp[i-1][j][1]+prices[i],dp[i-1][j][0])
# 2、今天【持有】股票，且此时最多进行了 j 次
# 第 i - 1 天【持有】股票，第 i 天不操作：dp[i][j][1]=dp[i-1][j][1]
# 第 i - 1 天【不持有】股票，第 i 天买入：dp[i][j][1]=dp[i-1][j-1][0]-prices[i]
dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i])
return dp[n-1][k][0]
leetcode309-最佳买卖股票时机含冷冻期（含有交易冷冻期）
注意点：
- 在卖出股票后，无法在第二天买入股票
- 不能同时参与多笔交易（在再次购买前出售掉之前的股票）
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
dp = [[0]*2 for _ in range(n)]
dp[0][1]=-prices[0]
dp[0][0]=0
for i in range(1,n):
dp[i][0]= max(dp[i-1][1]+prices[i],dp[i-1][0])
#和122个问题的逻辑点是相同的，唯一的区别就是这一行代码的差别，加入了一个if else的判断语句。
dp[i][1]= max(dp[i-1][1], (dp[i-2][0] if i >=2 else 0)-prices[i])
return dp[n-1][0]
leetcod714-买卖股票的最佳时期含手续费（每次交易含手续费）
加入了交易的手续费，k也是一个无限的交易次数，每笔都需要进行手续费
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
n = len(prices)
dp = [[0]*2 for _ in range(n)]
dp[0][1]=-prices[0]
dp[0][0]=0
for i in range(1,n):
#和122问题唯一的区别是这里减去了一个交易的费用问题
dp[i][0]= max(dp[i-1][1]+prices[i]-fee,dp[i-1][0])
dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])
return dp[n-1][0]