股票题库
买卖股票的最佳时机I
给定一个数组 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:
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
方案 动态规划
思路:
- 状态定义:
dp[i][j]表示下标为i这一天结束的时候，手上持股状态为j时，我们持有 的现金数。
j=0，表示当前不持股j=1, 表示当前持股
- 状态转移方程:
dp[i][0]:规定了今天不持股- 昨天不持股，今天什么也不做
- 昨天持股，今天卖出股票
- 方程为:
dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);
dp[i][1]:规定了今天持股- 昨天持股，今天什么也不做
- 昨天不持股，今天买入股票
- 方程为:
dp[i][1]=max(dp[i-1][1],-prices[i]);
- 初始化状态:
- dp初始化元素为0
- dp[0][0]为0，说明: 不持股显然为 0
- dp[0][1]=-prices[0],说明: 持股就需要减去第 1 天（下标为 0）的股价
- 问题答案:
dp[i][j]这个状态具有前缀的性质，下标为i的这一天计算结果包含了区间[0,i]所有的信息，因此可以输出dp[len-1][0]
:::details 优化空间前
function maxProfit(prices) {
let dp=new Array(prices.length).fill(0).map(()=>new Array(2).fill(0));
dp[0][0]=0;
dp[0][1]=-prices[0];
for(let i=1;i<prices.length;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]);
}
return dp[prices.length-1][0];
};
:::
性能分析:
- 时间复杂度：O(N)
- 空间复杂度：O(N)
:::details 优 化空间后
function maxProfit(prices) {
let dp=new Array(2);
dp[0]=0;
dp[1]=-prices[0];
for(let i=1;i<prices.length;i++){
dp[0]=Math.max(dp[0],dp[1]+prices[i]);
dp[1]=Math.max(dp[1],-prices[i]);
}
return dp[0];
};
:::
性能分析:
- 时间复杂度：O(n)
- 空间复杂度：O(1)
买卖股票的最佳时机 II
给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例1:
输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例2:
输入: prices = [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
方案 动态规划
思路:
- 状态定义:
dp[i][0]表示第i天交易完成后手里没有股票的最大利润dp[i][1]表示第i天交易完成后手里持有一只股票的最大利润
- 状态转移方程:
dp[i][0]，表示第i天交易完后手里没有股票，那么可能i-1天已经没有股票即dp[i-1][0],或者前一天有股票，我们将其卖出了即dp[i-1][1],这时候我们获得prices[i]的收益，由上可述得出:dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])dp[i][1], 表示第i天交易完成后手里持有股票，那么可能i-1天已经持有股票即dp[i-1][1],或者前一天没股票，我们将其买入即dp[i-1][0]，这时候我们减少prices[i]的收益，由上可述得出:dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])
- 初始化状态:
dp[0][0]=0,dp[0][1]=-prices[0] - 问题答案: 由于全部交易完成后，持有股票的收益一定低于不持有股票的收益，因此最后的答案为:
dp[n-1][0]
:::details 空间优化前
function maxProfit(prices) {
const len=prices.length;
let dp=new Array(len).fill(0).map(()=>new Array(2).fill(0));
dp[0][0]=0;
dp[0][1]=-prices[0];
for(let i=1;i<len;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]);
}
return dp[len-1][0];
};
:::
上面转移方程中，每一天的状态只与钱一天的状态有关，而与更早的状态无关，因此我们不 必存储这些无关的状态，只需要将dp[i-1][0]和dp[i-1][1]存放在两个变量中。
:::details 空间优化后
function maxProfit(prices) {
const len=prices.length;
dp0=0;
dp1=-prices[0];
for(let i=1;i<len;i++){
let newDp0=Math.max(dp0,dp1+prices[i]);
let newDp1=Math.max(dp1,dp0-prices[i]);
dp0=newDp0;
dp1=newDp1;
}
return dp0;
};
:::
性能分析:
- 时间复杂度：O(n)
- 空间复杂度：O(n) ，我们需要开辟 O(n) 空间存储动态规划中的所有状态。如果使用空间优化，空间复杂度可以优化至 O(1)。
买卖股票的最佳时机 III
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例1:
输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例2:
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
方案 动态规划
思路:
- 状态定义:
dp[i][0]表示第i天进行过一次买操作后的最大利润dp[i][1]表示第i天进行了一次买操作和卖操作后的最大利润dp[i][2]表示第i天进行了一次买卖操作后，又进行了一次买操作dp[i][3]表示第i天进行了两次买卖操作
- 状态转移方程:
dp[i][0]为:max(dp[i][0],dp[i][0]-prices[i])dp[i][1]为:max(dp[i][1],dp[i][0]+prices[i])dp[i][2]为:max(dp[i][2],dp[i][1]-prices[i])dp[i][3]为:max(dp[i][3],dp[i][2]+prices[i])
- 初始状态:
- dp[i][0]=-prices[0];
- dp[i][1]=0;
- dp[i][2]=-prces[0];
- dp[i][3]=0;
- 问题答案: dp[i][3]
:::details 空间优化前
function maxProfit(prices) {
const len=prices.length;
let dp=new Array(len).fill(0).map(()=>new Array(4).fill(0));
dp[0][0]=-prices[0];
dp[0][1]=0;
dp[0][2]=-prices[0];
dp[0][3]=0;
for(let i=1;i<len;i++){
dp[i][0]=Math.max(dp[i-1][0],-prices[i]);
dp[i][1]=Math.max(dp[i-1][1],dp[i][0]+prices[i]);
dp[i][2]=Math.max(dp[i-1][2],dp[i][1]-prices[i]);
dp[i][3]=Math.max(dp[i-1][3],dp[i][2]+prices[i]);
}
return dp[len-1][3];
};
:::
:::details 空间优化后
function maxProfit(prices) {
const len=prices.length;
buy1=-prices[0];
sell1=0;
buy2=-prices[0];
sell2=0;
for(let i=1;i<len;i++){
buy1=Math.max(buy1,-prices[i]);
sell1=Math.max(sell1,buy1+prices[i]);
buy2=Math.max(buy2,sell1-prices[i]);
sell2=Math.max(sell2,buy2+prices[i]);
}
return sell2;
};
:::
性能分析:
- 时间复杂度：O(n)，其中 n 是数组 prices 的长度。
- 空间复杂度：O(1)。
买卖股票的最佳时机 IV
给定一个整数数组 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 。
方案 动态规划
思路:
- 状态定义:
buy[i][j]表示对于数组prices[0,,i]中的价格而言，进行恰好j笔交易，并且当前手上持有一只股票这种情况下的最大利润sell[i][j]表示对于数组prices[0,,i]中的价格而言，进行恰好j笔交易，并且当前手上不持有股票，这种情况下的最大利润
- 状态转移方程:
- 对于
buy[i][j]:如果持有的股票是第i天买入的，那么i-1天时不持有股票，对应状态sell[i-1][j]，并且需要扣除prices[i]的买入花费;如果不是第i天买入的，那么在i-1天我们持有股票，对应状态buy[i-1][j],可得方程为:buy[i][j]=max(buy[i-1][j],sell[i-1][j]-prices[i]) - 对于
sell[i][j]:如果持有的股票是第i天卖出的，那么i-1天时我们持有股票，对应状态buy[i-1][j-1],并且需要增加prices[i]的卖出收益；如果不是第i天卖出的，那么在第i-1天时我们手上不持有股票，对应状态sell[i-1][j],可得方程为:sell[i][j]=max(sell[i-1][j],buy[i-1][j-1]+prices[i])
- 初始化状态:
- buy[0][1,,k] 为无穷小,buy[0][0]=0;
- sell[0][1,,k] 为无穷小,sell[0][0]=0;
- 问题答案:在所有的
n天结束后，手上不持有股票对应的最大利润一定是最大利润，然而完成的交易并不是越多越好的，所以最终的答案即为`sell[n-1][0,,,k]中的最大值
:::details 空间优化前
function maxProfit(k, prices) {
const len=prices.length;
if(!len){
return 0;
}
k=Math.min(k,Math.floor(len/2));
const buy=new Array(len).fill(0).map(()=>new Array(k+1).fill(0));
const sell=new Array(len).fill(0).map(()=>new Array(k+1).fill(0));
buy[0][0]=-prices[0];
sell[0][0]=0;
for(let i=1;i<=k;i++){
buy[0][i]=sell[0][i]=-Infinity;
}
for(let i=1;i<len;i++){
buy[i][0]=Math.max(buy[i-1][0],sell[i-1][0]-prices[i]);
for(let j=1;j<=k;j++){
buy[i][j]=Math.max(buy[i-1][j],sell[i-1][j]-prices[i]);
sell[i][j]=Math.max(sell[i-1][j],buy[i-1][j-1]+prices[i])
}
}
return Math.max(...sell[len-1]);
};
:::
:::details 空间优化后
function maxProfit(k, prices) {
const len=prices.length;
if(!len){
return 0;
}
k=Math.min(k,Math.floor(len/2));
const buy=new Array(k+1).fill(0);
const sell=new Array(k+1).fill(0);
buy[0]=-prices[0];
sell[0]=0;
for(let i=1;i<=k;i++){
buy[i]=sell[i]=-Infinity;
}
for(let i=1;i<len;i++){
buy[0]=Math.max(buy[0],sell[0]-prices[i]);
for(let j=1;j<=k;j++){
buy[j]=Math.max(buy[j],sell[j]-prices[i]);
sell[j]=Math.max(sell[j],buy[j-1]+prices[i])
}
}
return Math.max(...sell);
};
:::
性能分析:
- 时间复杂度：O(nmin(n,k))，其中 n 是数组prices的大小，即我们使用二重循环进行动态规划需要的时间。
- 空间复杂度：O(nmin(n,k)) 或 O(min(n,k))，取决于我们使用二维数组还是一维数组进行动态规划。
最佳买卖股票时机含冷冻期
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:
输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
方案 动态规划
思路:
- 状态定义:
dp[i][j]表示第i天结束之后的累计最大收益 - 状态转移方程:
dp[i][0]表示目前持有一只股票对应的累计最大收益，方程为:dp[i][0]=max(dp[i-1][0],dp[i-1][2]-prices[i])dp[i][1]表示目前不持有任何股票，并且处于冷冻期中，对应的累计最大收益，方程为:dp[i][1]=dp[i-1][0]+prices[i]dp[i][2]表示目前不持有任何股票，并且不处于冷冻期中，对应的累计最大收益，方程为:dp[i][2]=max(dp[i-1][1],dp[i-1][2])
- 初始状态:
- dp[0][0]=-prices[0]
- dp[0][1]=0
- dp[0][2]=0
- 问题答案:
- 如果一共有n天，最终答案为
max(dp[n-1][0],dp[n-1][1],dp[n-1][2]) - 但是最后一天结束后，手上仍然持有股票，显然是没有意义的，因此，只需要比较
max(dp[n-1][1],dp[n-1][2])
:::details 空间优化前
function maxProfit(prices) {
const len=prices.length;
if(!len){
return 0;
}
const dp=new Array(len).fill(0).map(()=>new Array(3).fill(0));
dp[0][0]=-prices[0];
dp[0][1]=0;
dp[0][2]=0;
for(let i=1;i<len;i++){
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][2]-prices[i]);
dp[i][1]=dp[i-1][0]+prices[i];
dp[i][2]=Math.max(dp[i-1][1],dp[i-1][2]);
}
return Math.max(dp[len-1][1],dp[len-1][2]);
};
:::
上述状态转移方程中，dp[i][,,,]只与dp[i-1][,,,]有关
:::details 空间优化后
function maxProfit(prices) {
const len=prices.length;
if(!len){
return 0;
}
const dp=new Array(3).fill(0);
dp[0]=-prices[0];
dp[1]=0;
dp[2]=0;
for(let i=1;i<len;i++){
const newDp=new Array(3).fill(0);
newDp[0]=Math.max(dp[0],dp[2]-prices[i]);
newDp[1]=dp[0]+prices[i];
newDp[2]=Math.max(dp[1],dp[2]);
dp[0]=newDp[0];
dp[1]=newDp[1];
dp[2]=newDp[2];
}
return Math.max(dp[1],dp[2]);
};
:::
性能分析:
- 时间复杂度：O(n)，其中 n 为数组 prices 的长度。
- 空间复杂度：O(n)。我们需要 3n 的空间存储动态规划中的所有状态，对应的空间复杂度为 O(n)。如果使用空间优化，空间复杂度可以优化至 O(1)。
买卖股票的最佳时机含手续费
给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
示例1:
输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
输出：8
解释：能够达到的最大利润:
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8
示例2:
输入：prices = [1,3,7,5,10,3], fee = 3
输出：6
方案 动态规划
思路:
- 状态定义:
dp[i][0]表示第i天交易完后手里没有股票的最大利润dp[i][1]表示第i天交易完后手里持有一支股票的最大利润（i 从 0 开始）
- 状态转移方程:
dp[i][0]: 表示第i天不持有股票，如果第i-1天也不持有股票即dp[i-1][0],如果第i-1天持有股票，这时候我们将其卖出，获得prices[i]收益,但需要支付fee的手续费，由上可得状态转移方程:dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]-fee)dp[i][1]: 表示第i天持有股票，如果第i-1天已经持有股票即dp[i-1][1],如果第i-1天不持有股票，这时候我们将其买入,减少prices[i]收益，由上可得状态转移方程:dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])
- 初始化状态:
- dp[0][0]=0,
- dp[0][1]=-prices[0]
- 问题答案:全部交易结束后，持有股票的收益一定低于不持有股票的收益，因此这时候dp[n-1][0]的收益一定是最大的
:::details 空间优化前
function maxProfit(prices, fee) {
const len=prices.length;
const dp=new Array(len).fill(0).map(()=>new Array(2).fill(0));
dp[0][0]=0;
dp[0][1]=-prices[0];
for(let i=1;i<len;i++){
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]-fee);
dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
}
return dp[len-1][0];
};
:::
上述状态转移方程中，dp[i][0]和dp[i][1] 只会从dp[i-1][0]和dp[i-1][1]转移而来，所以我们可以使用滚动数组来优化空间
:::details 空间优化后
function maxProfit(prices, fee) {
const len=prices.length;
dp0=0;
dp1=-prices[0];
for(let i=1;i<len;i++){
let newDp0=Math.max(dp0,dp1+prices[i]-fee);
let newDp1=Math.max(dp1,dp0-prices[i]);
dp0=newDp0;
dp1=newDp1;
}
return dp0;
};
:::
性能分析: