- Notifications
You must be signed in to change notification settings - Fork24
Open
Description
上面这 6 道题目可以归为一道题目来看，与现实略有不同，题目中添加了一些限制条件，读完题分析后不难发现。
- 第一题只交易一次，也就是 k = 1。
- 第二题不限制交易次数，也就是 k = +infinity。
- 第三题只交易两次，也就是 k = 2。
- 第四道限制最多次数为 k。
- 第五道和第六道不限次数，相当于在第二题的基础上分别添加了交易
冷冻期和手续费的额外条件。
我们每天能做的操作无非是以下这三种：
- 买入
- 卖出
- 无操作
不过要注意以下四点限制条件。
要先买入才能卖出。- 题目要求不能同时参与多笔交易，也就是说
再次买入前需要卖出手中持有的股票。 - 无操作基于两种状态，
手中持有股票和没有持有股票。 - 交易次数 k 也有限制，
只有 k >= 0 时才可以买入。
分析好了这些状态，接下来就是翻译成代码了。
首先，我们可以建立一个三维数组来表示上面的这些状态，先来明确一些变量含义。
- i: 天数 范围是 (0 <= i <= n - 1)
- k: 最大交易次数
- 0: 没有持有股票
- 1: 持有股票
- n: 股票数组长度
dp[i][k][0]dp[i][k][1]// 举个🌰dp[2][2][1]// 今天是第 2 天，手中持有股票，最多还可以进行 2 次交易
我们最终要求的可获得的最大收益就是dp[n - 1][k][0]，代表最后一天将股票卖出后的最大收益。(这里卖出一定比持有收益更大，所以是 [0]，而不是 [1])
接下来，我们尝试列出状态转移方程。
// 今天手中没有持有股票，有两种可能：// 1. 昨天没有持有，今天选择不操作。 对应: dp[i - 1][k][0]// 2. 昨天持有，今天卖出了，所以今天没有股票了。对应: dp[i - 1][k][1] + prices[i]dp[i][k][0]=Math.max(dp[i-1][k][0],dp[i-1][k][1]+prices[i])// 今天手中持有股票，有两种可能：// 1. 昨天手中持有股票，今天选择不操作。对应: dp[i - 1][k][1]// 2. 昨天没有持有股票，今天买入了。对应: dp[i - 1][k - 1][0] - prices[i]dp[i][k][1]=Math.max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i])
很显然，卖出股票利润增加，买入股票利润减少。因为每次交易包含两次成对的操作，买入和卖出。
所以只有买入的时候需要将 k - 1，那么最大利润就是上面这两种可能性中的最大值。
第一题 k = 1
将状态转移方程套入本题的条件，k = 1，列出状态转移方程。
dp[i][1][0]=Math.max(dp[i-1][1][0],dp[i-1][1][1]+prices[i])dp[i][1][1]=Math.max(dp[i-1][1][1],dp[i-1][0][0]-prices[i])=Math.max(dp[i-1][1][1],-prices[i])// k = 0 时，dp[i - 1][0][0] = 0
观察发现 k 既然都是 1 且不会改变，也就是说 k 对状态转移已经没有影响了，我们可以进一步化简方程。
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i])dp[i][1]=Math.max(dp[i-1][1],-prices[i])
对于第 0 天，我们需要进行初始化：
- 不持有：
dp[0][0] = 0 - 持有：
dp[0][1] = -prices[0] (花了 prices[0] 的钱买入股票)
constmaxProfit=function(prices){letn=prices.lengthletdp=Array.from(newArray(n),()=>newArray(2))dp[0][0]=0dp[0][1]=-prices[0]for(leti=1;i<n;i++){dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i])dp[i][1]=Math.max(dp[i-1][1],-prices[i])}returndp[n-1][0]}
- 时间复杂度：O(n)
- 空间复杂度：O(n)
我们发现在转移的时候，dp[i] 只会从dp[i - 1] 转移得来，因此第一维可以去掉，空间复杂度优化到 O(1)。
constmaxProfit=function(prices){letn=prices.lengthletdp=Array.from(newArray(n),()=>newArray(2))dp[0]=0dp[1]=-prices[0]for(leti=1;i<n;i++){dp[0]=Math.max(dp[0],dp[1]+prices[i])dp[1]=Math.max(dp[1],-prices[i])}returndp[0]}
- 时间复杂度：O(n)
- 空间复杂度：O(1)
我们也可以将变量名变得更加友好一些。
- profit_out：卖出时的利润
- profit_in：买入时的利润
constmaxProfit=function(prices){letn=prices.lengthletprofit_out=0letprofit_in=-prices[0]for(leti=1;i<n;i++){profit_out=Math.max(profit_out,profit_in+prices[i])profit_in=Math.max(profit_in,-prices[i])}returnprofit_out}
- 时间复杂度：O(n)
- 空间复杂度：O(1)
第二题 k = +infinity
将状态转移方程套入本题的条件，k = +infinity。
dp[i][k][0]=Math.max(dp[i-1][k][0],dp[i-1][k][1]+prices[i])dp[i][k][1]=Math.max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i])=Math.max(dp[i-1][k][1],dp[i-1][k][0]-prices[i])
我们发现数组中的 k 同样已经不会改变了，也就是说 k 对状态转移已经没有影响了，可以进一步化简方程。
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i])dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i])
对于第 0 天，我们要给出初始值：
- 不持有：
dp[0][0] = 0 - 持有：
dp[0][1] = -prices[0] (花了 prices[0] 的钱买入股票)
constmaxProfit=function(prices){letn=prices.lengthletdp=Array.from(newArray(n),()=>newArray(2))dp[0][0]=0dp[0][1]=-prices[0]for(leti=1;i<n;i++){dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i])dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i])}returndp[n-1][0]}
同样在转移的时候，dp[i] 只会从 dp[i - 1] 转移得来，因此第一维可以去掉，空间复杂度优化到 O(1)。
constmaxProfit=function(prices){letn=prices.lengthletdp=Array.from(newArray(n),()=>newArray(2))dp[0]=0dp[1]=-prices[0]for(leti=1;i<n;i++){lettmp=dp[0]// 中间变量可省略，因为当天买入卖出不影响结果dp[0]=Math.max(dp[0],dp[1]+prices[i])dp[1]=Math.max(dp[1],tmp-prices[i])}returndp[0]}
同上题一样，我们可以将变量名变得更加友好一些。
constmaxProfit=function(prices){letn=prices.lengthletprofit_out=0letprofit_in=-prices[0]for(leti=1;i<n;i++){profit_out=Math.max(profit_out,profit_in+prices[i])profit_in=Math.max(profit_in,profit_out-prices[i])}returnprofit_out}
第三题 k = 2
前面两种情况，无论是 k = 1，还是 k = +infinity 的情况下，k 对状态转移方程是没有影响的。
不过当 k = 2 时，k 就对状态转移方程有影响了。列出状态转移方程：
dp[i][k][0]=Math.max(dp[i-1][k][0],dp[i-1][k][1]+prices[i])dp[i][k][1]=Math.max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i])
这个时候 k 无法化简，我们需要使用两次循环对 k 进行穷举。
for(leti=0;i<n;i++){for(letk=maxK;k>=1;k--){dp[i][k][0]=Math.max(dp[i-1][k][0],dp[i-1][k][1]+prices[i])dp[i][k][1]=Math.max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i])}}
不过因为 k 的取值范围比较小，我们也可以直接将它们全部列举出来。
dp[i][2][0]=Math.max(dp[i-1][2][0],dp[i-1][2][1]+prices[i])dp[i][2][1]=Math.max(dp[i-1][2][1],dp[i-1][1][0]-prices[i])dp[i][1][0]=Math.max(dp[i-1][1][0],dp[i-1][1][1]+prices[i])dp[i][1][1]=Math.max(dp[i-1][1][1],dp[i-1][0][0]-prices[i])=Math.max(dp[i-1][1][1],-prices[i])
有了上面两道题的铺垫，我们后面几道题就直接写出降维后的解法。
constmaxProfit=function(prices){letn=prices.lengthletdp_i10=0letdp_i11=-prices[0]letdp_i20=0letdp_i21=-prices[0]for(leti=1;i<n;i++){dp_i20=Math.max(dp_i20,dp_i21+prices[i])dp_i21=Math.max(dp_i21,dp_i10-prices[i])dp_i10=Math.max(dp_i10,dp_i11+prices[i])dp_i11=Math.max(dp_i11,-prices[i])}returndp_i20}
同上面一样，我们可以将变量名变得更加友好一些。
constmaxProfit=function(prices){letprofit_1_in=-prices[0],profit_1_out=0letprofit_2_in=-prices[0],profit_2_out=0letn=prices.lengthfor(leti=1;i<n;i++){profit_2_out=Math.max(profit_2_out,profit_2_in+prices[i])profit_2_in=Math.max(profit_2_in,profit_1_out-prices[i])profit_1_out=Math.max(profit_1_out,profit_1_in+prices[i])profit_1_in=Math.max(profit_1_in,-prices[i])}returnprofit_2_out}
第四题 k 是任意数
一个有收益的交易至少需要两天（在前一天买入，在后一天卖出，前提是买入价格低于卖出价格）。
如果股票价格数组的长度为 n，则有收益的交易的数量最多为 n / 2（整数除法）。因此 k 的临界值是 n / 2。
如果给定的 k 不小于临界值，即 k >= n / 2，则可以将 k 扩展为正无穷，也就是第二题的情况，如下函数 maxProfit2。
constmaxProfit=function(k,prices){letn=prices.lengthconstmaxProfit2=function(prices){letprofit_out=0letprofit_in=-prices[0]for(leti=1;i<n;i++){profit_out=Math.max(profit_out,profit_in+prices[i])profit_in=Math.max(profit_in,profit_out-prices[i])}returnprofit_out}if(k>n/2){returnmaxProfit2(prices)}letprofit=newArray(k)// 初始化买入卖出时的利润，将每次交易买入、卖出时的利润放在一个对象中，实现降维for(letj=0;j<=k;j++){profit[j]={profit_in:-prices[0],profit_out:0}}for(leti=0;i<n;i++){for(letj=1;j<=k;j++){profit[j]={profit_out:Math.max(profit[j].profit_out,profit[j].profit_in+prices[i]),profit_in:Math.max(profit[j].profit_in,profit[j-1].profit_out-prices[i])}}}returnprofit[k].profit_out}
第五题 k 为正无穷但有冷却时间
每次卖出之后都要等一天才能继续交易，也就是第 i 天选择买的时候，要从 i - 2 状态转移。
列出状态转移方程。
dp[i][k][0]=Math.max(dp[i-1][k][0],dp[i-1][k][1]+prices[i])dp[i][k][1]=Math.max(dp[i-1][k][1],dp[i-2][k-1][0]-prices[i])=Math.max(dp[i-1][k][1],dp[i-2][k][0]-prices[i])
k 同样对状态转移已经没有影响了，可以进一步化简方程。
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i])dp[i][1]=Math.max(dp[i-1][1],dp[i-2][0]-prices[i])
constmaxProfit=function(prices){letn=prices.lengthletdp_i0=0letdp_i1=-prices[0];letdp_pre=0// 代表 dp[i-2][0]for(leti=0;i<n;i++){lettmp=dp_i0dp_i0=Math.max(dp_i0,dp_i1+prices[i])dp_i1=Math.max(dp_i1,dp_pre-prices[i])dp_pre=tmp}returndp_i0}
同上面一样，我们可以将变量名变得更加友好一些。
constmaxProfit=function(prices){letn=prices.lengthletprofit_in=-prices[0]letprofit_out=0letprofit_freeze=0for(leti=1;i<n;i++){lettemp=profit_outprofit_out=Math.max(profit_out,profit_in+prices[i])profit_in=Math.max(profit_in,profit_freeze-prices[i])profit_freeze=temp}returnprofit_out}
第六题 k 为正无穷但有手续费
在第二题的基础上，添加了手续费。
每次交易要支付手续费，只要把手续费从利润中减去即可，可以列出如下两种方程。
第一种方程：在每次买入股票时扣除手续费
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)
第二种方程：在每次卖出股票时扣除手续费
dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]-fee)dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])
constmaxProfit=function(prices,fee){letn=prices.lengthletdp=Array.from(newArray(n),()=>newArray(2))dp[0]=0dp[1]=-prices[0]for(leti=1;i<n;i++){lettmp=dp[0]dp[0]=Math.max(dp[0],dp[1]+prices[i]-fee)dp[1]=Math.max(dp[1],tmp-prices[i])}returndp[0]}
同上面一样，我们可以将变量名变得更加友好一些。
constmaxProfit=function(prices,fee){letprofit_out=0letprofit_in=-prices[0]for(leti=1;i<prices.length;i++){profit_out=Math.max(profit_out,profit_in+prices[i]-fee)profit_in=Math.max(profit_in,profit_out-prices[i])}returnprofit_out}
站在巨人的肩膀上
Metadata
Metadata
Assignees
Labels
No labels