Python每日一练-----买卖股票的最佳时机Ⅳ
⛅（day20）
目录
🖍题目：
题目分析：
解题思路：
🌈动态规划解法
✏代码注释
🌈代码优化
代码实现
✏代码注释
🖍题目：
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
🌠示例 1:
输入：k = 2, prices = [2,4,1]
输出：2
说明：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
🌠示例 2:
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
说明：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
题目分析：
给定整数k，和整数数组prices，在最多进行k次交易的前提下，交易获取最大利益。这里的一次交易指的是一次买进和一次出售。值得注意的是这里的k可能取到10^9甚至更多，然而对于过大的k是没有意义的，因为n天最多能进行[n/2]次交易，（这里的[]表示取整）。
为什么最多是[n/2]次交易？
因为n天进行超过[n/2]次交易会存在同一天买进和买出的情况。比如prices = [ 1，2，3]，k = 2 > [3/2] = 1。取这时最大利润 = （2-1）+（3-1）= 2等同于，最大利润 = 3-1= 2。这时k = 1于k = 2获得的利润是一样的，第二天出现无效交易（在同一天买进又卖出，利润为0）。所以我们认为在不进行无效交易的情况下，n天最多能进行[n/2]次交易。
解题思路：
动态规划解法
进行动态规划五步曲
✨1.分析确定dp数组以及其下标的含义或状态分析
对于给定的整数k和数组prices，我们的第一直觉就是使用二维dp[i][j]数组。
现在我们规定：
buyProfit[i][j]表示在第i天进行了j次交易，且手上持有股票的状态下获取到的最大利润
sellProfit[i][j]表示在第i天进行了j次交易，且手上不持有股票的状态下获取到的最大利润
✨2.确定递推公式
接着进行状态的分析
对于buyProfit[i][j]
（1）如果持有的股票是在第i天买入
那么在第i-1天包括第i-1天前，进行了j次交易（因为买入未构成一次交易）。在第i-1天不次有股票，在底i天买入股票需要花费prices[i]。==> sellProfit[i - 1][j] - prices[i]
（2）如果持有的股票不是在第i天买入
那么在第i-1天包括第i-1天前，进行了j次交易（因为买入未构成一次交易）。在第i天无任何买卖。==> buyProfit[i - 1][j]
buyProfit[i][j] = max（buyProfit[i - 1][j]，sellProfit[i - 1][j] - prices[i]）用max取两者最大值
对于sellProfit[i][j]
（1）如果不持有的股票是因为在第i天卖出
那么在第i-1天时只进行了j-1次交易，在第i天卖出股票获得prices[i] 。==>buyProfit[i - 1][j - 1] + prices[i]
（1）如果不持有的股票不是因为在第i天卖出
那么在第i-1天进行了j次交易，第i天无任何买卖。==>sell[i-1][j]
sellProfit[i][j] = max (sell[i-1][j]，buyProfit[i - 1][j - 1] + prices[i])
递推公式：
buyProfit[i][j] = max（buyProfit[i - 1][j]，sellProfit[i - 1][j] - prices[i]）
sellProfit[i][j] = max (sell[i-1][j]，buyProfit[i - 1][j - 1] + prices[i])
✨3.如何初始化dp数组
如何初始化dp（buyProfit，sellProfit）数组？
我们考虑边界条件和dp数组的基础，第0天和交易次数为0时
对于第0天（也就是第一天，为方便以下标表示第几天）
不论进行几次交易，利润都为0。但是对于buyProfit手中持有股票的情况来说，在第0天一定是以prices[0]的价格买进股票。
所以初始化buyProfit[0][k]
当k = 0时
buyProfit[0][0] = -prices[0]
当k != 0时
我们知道无论k为多少，进行多少次交易都为无效交易，即利润为0.所以可以将buyProfit[0][k]初始化成不合理的数，如负无穷。这样在初始化用max取最大值时保证取到的是-prices[i]（k != 0）
初始化sellProfit[0][k]
当k = 0时
sellProfit[0][0]一定等于0，这样才能满足在第0天不持又股票
当k != 0时
我们知道无论k为多少，进行多少次交易都为无效交易，所以也可以将buyProfit[0][k]初始化成不合理的数，如负无穷。
那么为什设置为负无穷而不设为0呢？
我们知道有些交易是会出现负利润的情况的，如果设为0，在max（）取最大值时会取0，增大结果，使结果出错。
对于进行0次交易
初始化buyProfit[i][0]
因为是没有交易进行，那么我们只有两种操作，一种是不进行任何操作，第二种是只买进一次（这时没有卖的操作还不算交易）。
不进行任何操作
继承前一天的状态==>buyProfit[i-1][0]
只买进一次
sellProfi[i-1][0] - prices[i]
初始化sellProfit[i][0]
不进行任何操作
sellProfit[i-1][0]
只买进一次
因为sellProfit表示不持有股票的状态所以可以去掉这一状态
最终初始化
buyProfit[0][0] = -prices[0]sellProfit[0][0] = 0buyProfit[0][i] = float("-inf")sellProfit[0][i] = float("-inf")buyProfit[i][0] = max(buyProfit[i - 1][0], sellProfit[i - 1][0] - prices[i])sellProfit[i][0] = sellProfit[i - 1][0]✨4.确定遍历的顺序
由递推公式可知，递推方向为首到尾
✨5.举例验证推导的dp数组（公式）是否正确
可以带入一个简单以的例子，比如例1.
那么最终的答案是什么呢？
可以肯定的是最终答案在sellProfit[n-1][1.....k]（n为数组prices的长度）中，即递推完成状态。因为抛售后获得的利润一定会比将股票留在手里获得的利润高。所以最后返回sellProfit[n-1][1.....k]最大值即可。return max(sellProfit[n-1])
代码实现
🌈动态规划解法
def maxProfit(k, prices): if not prices: return 0 n = len(prices) k = min(k, n // 2) buyProfit = [[0] * (k + 1) for _ in range(n)] sellProfit = [[0] * (k + 1) for _ in range(n)] buyProfit[0][0] = -prices[0] sellProfit[0][0] = 0 for i in range(1, k + 1): buyProfit[0][i] = float("-inf") sellProfit[0][i] = float("-inf") for i in range(1, n): buyProfit[i][0] = max(buyProfit[i - 1][0], sellProfit[i - 1][0] - prices[i]) sellProfit[i][0] = sellProfit[i - 1][0] for j in range(1, k + 1): buyProfit[i][j] = max(buyProfit[i - 1][j], sellProfit[i - 1][j] - prices[i]) sellProfit[i][j] = max(sellProfit[i - 1][j], buyProfit[i - 1][j - 1] + prices[i]) return max(sellProfit[n - 1])✏代码注释
def maxProfit(k, prices): if not prices: # 空数组，则返回0 return 0 n = len(prices) k = min(k, n // 2) # 取最大交易次数 buyProfit = [[0] * (k + 1) for _ in range(n)] # 创建dp二维数组 sellProfit = [[0] * (k + 1) for _ in range(n)] buyProfit[0][0] = -prices[0] # 初始化第0天和第无交易时dp数组 sellProfit[0][0] = 0 # 初始化第0天且k>0时的dp数组 for i in range(1, k + 1): # i=0已在初始化中讨论 buyProfit[0][i] = float("-inf") # floa("-inf")表示负无穷，floa("+inf")标识正无穷，floa("inf")表示无穷 sellProfit[0][i] = float("-inf") # 初始化无交易状态 for i in range(1, n): # i=0已在初始化中讨论，且受限于[i-1],所以i从1开始 buyProfit[i][0] = max(buyProfit[i - 1][0], sellProfit[i - 1][0] - prices[i]) sellProfit[i][0] = sellProfit[i - 1][0] # 带入dp递归公式 for j in range(1, k + 1): # 且受限于[j-1],所以j从1开始 buyProfit[i][j] = max(buyProfit[i - 1][j], sellProfit[i - 1][j] - prices[i]) sellProfit[i][j] = max(sellProfit[i - 1][j], buyProfit[i - 1][j - 1] + prices[i]) return max(sellProfit[n - 1])这里说明一下为什么创建dp数组时是[0]*(k+1)而不是[0]*k。对于单调递减的数组，如果交易就会亏钱，所以不交易才能获得最大利益。这时候最多进行k次交易在加上不交易这种情况dp数组的维数就是k+1.
🌈代码优化
注意到buyProfit[i][j] 和 sell[i][j]sell[i][j] 都从 buy[i-1][..]以及sell[i−1][..] 转移而来，因此我们可以使用一维数组而不是二维数组进行状态转移，这样能提高解题效率。
这里说的转移就是状态的变换，从状态[i-1]到状态[i]的变化。
buyProfit[i][j] = max(buyProfit[i - 1][j], sellProfit[i - 1][j] - prices[i])
可转化为
buyProfit[j] = max(buyProfit[j], sellProfit([j] - prices[i])
----------------------------------------------------------------------------------------------
sellProfit[i][j] = max(sellProfit[i - 1][j], buyProfit[i - 1][j - 1] + prices[i])
可转化为
sellProfit[j] = max(sellProfit[j], buyProfit[j - 1] + prices[i])
考虑状态覆盖的问题（赋值先后）
对于转换后的dp公式
buyProfit[j] = max(buyProfit[j], sellProfit([j] - prices[i])
sellProfit[j] = max(sellProfit[j], buyProfit[j - 1] + prices[i])
因为先计算buyProfit[j]，所以当下一步计算sellProfit[j]时sellProfit[j]公式中的buyProfit[j - 1]的值已经被覆盖了。从二维数组理解就是
sellProfit[j]公式中的buyProfit[j - 1]本来应当是从二维表示中的buyProfit[i-1][j-1]转移而来，而现在却变成了 buyProfit[i][j−1]。
但是实际上它仍是正确的
考察buyProfit[i][j−1] = max(buyProfit[i - 1][j-1], sellProfit[i - 1][j-1] - prices[i])
仍是从状态[i-1]到状态[i]的变化，所以等效于buyProfit[j - 1]
代码实现
def maxProfit(k, prices): if not prices: return 0 n = len(prices) k = min(k, n // 2) buyProfit = [0] * (k + 1) sellProfit = [0] * (k + 1) buyProfit[0], sellProfit[0] = -prices[0], 0 for i in range(1, k + 1): buyProfit[i] = sellProfit[i] = float("-inf") for i in range(1, n): buyProfit[0] = max(buyProfit[0], sellProfit[0] - prices[i]) for j in range(1, k + 1): buyProfit[j] = max(buyProfit[j], sellProfit[j] - prices[i]) sellProfit[j] = max(sellProfit[j], buyProfit[j - 1] + prices[i]) return max(sellProfit)✏代码注释
def maxProfit(k, prices): if not prices: # 空数组，则返回0 return 0 n = len(prices) k = min(k, n // 2) # 取最大交易次数 buyProfit = [0] * (k + 1) # 创建dp一维数组 sellProfit = [0] * (k + 1) buyProfit[0], sellProfit[0] = -prices[0], 0 # 初始化第0天时dp数组 for i in range(1, k + 1): buyProfit[i] = sellProfit[i] = float("-inf") for i in range(1, n): # i=0已在初始化中讨论，且受限于[i-1],所以i从1开始 buyProfit[0] = max(buyProfit[0], sellProfit[0] - prices[i]) for j in range(1, k + 1): # 且受限于[j-1],所以j从1开始 buyProfit[j] = max(buyProfit[j], sellProfit[j] - prices[i]) sellProfit[j] = max(sellProfit[j], buyProfit[j - 1] + prices[i]) return max(sellProfit)今天就到这，明天见。🚀
❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄end❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄