买卖股票

发表于2024-07-09更新于2024-07-10

买卖股票

买卖股票最佳时机（121）

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/

图 0

思路
股票只能买卖一次

  • 1、dp[i][0],dp[i][1] 分别表示持有股票和不持有股票的现金最大值
  • 2、递推公式：
    • dp[i][0] = max(dp[i-1][0],-prices[i]) 维持前一天持有股票的状态或者买入今天的股票，这是因为只能买一次买一次所以是-prices[i]
    • dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i]) 维持前一天不持有股票的状态，或者在今天卖出股票
  • 3、初始化，dp[0][0] = -prices[0]
  • 4、dp[i]的状态依赖dp[i-1]的状态因此从前往后遍历
    可以把二维dp数组压缩为一维如下代码所示
1
2
3
4
5
6
7
8
9
10
11
var maxProfit = function(prices) {
  let dp = Array(2).fill(0)
  dp[0] = -prices[0]
  let n = prices.length
  for(let i=1;i<n;i++ ){
    let val0 = Math.max(dp[0],-prices[i])
    let val1 = Math.max(dp[0]+prices[i],dp[1])
    dp = [val0,val1]
  }
  return dp[1]
};

买卖股票的最佳时机（122）

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/

图 1

思路
股票只能买卖多次

  • 1、dp[i][0],dp[i][1] 分别表示持有股票和不持有股票的现金最大值
  • 2、递推公式：
    • 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]) 维持前一天不持有股票的状态，或者在今天卖出股票
  • 3、初始化，dp[0][0] = -prices[0]
  • 4、dp[i]的状态依赖dp[i-1]的状态因此从前往后遍历
    可以把二维dp数组压缩为一维如下代码所示
1
2
3
4
5
6
7
8
9
10
11
12
13
var maxProfit = function(prices) {
  let n = prices.length
  let dp = Array(2).fill(0)
  dp[0] = -prices[0]
  for (let i = 1;i<n;i++){

    let val0 = Math.max(dp[0],dp[1]-prices[i])
    let val1 = Math.max(dp[0]+prices[i],dp[1])
    dp = [val0,val1]
    console.log(dp)
  }
  return dp[1]
};

买卖股票的最佳时机（123）

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/

图 2

思路
关键在于至多买卖两次，这意味着可以买卖一次，可以买卖两次，也可以不买卖

  • 1、dp数组状态：dp[i][0],dp[i][1],dp[i][2],dp[i][3],dp[i][4]
    • 0：没有操作
    • 1：第一天持有股票
    • 2：第一天不持有股票
    • 3：第二次持有股票
    • 4：第二次不持有股票
  • 2、递推公式
    • dp[i][0] = dp[i-1][0]
    • dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i]) 保持前一天持有状态，今天刚刚买入。
    • max(dp[i-1][1] + prices[i],dp[i-1][2]) 延续前一天不持有的状态或者，前一天持有今天买了
    • max(dp[i-1][3],dp[i-1][2]-prices[i])，延续前一天买入第二次股票的状态，前一天第一次不持有减去今天股票价格
    • max(dp[i-1][4],dp[i-1][3]+prices[i])
  • 3、初始化：
    • dp[0][0] = 0
    • dp[0][1] = -prices[0]
    • dp[0][2] = 0,同一天买卖，手里现金增加0
    • dp[0][3] = -prices[0],第一天买入，卖出，又买入
    • dp[0][4] = 0
  • 4、遍历：从前往后
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var maxProfit = function(prices) {
  let n = prices.length
  let dp = Array(5).fill(0)
  dp[1] = -prices[0]
  dp[3] = -prices[0]
  for(let i=1;i<n;i++){
    let val0 = dp[0]
    let val1 = Math.max(dp[0] - prices[i],dp[1])
    let val2 = Math.max(dp[1]+prices[i],dp[2])
    let val3 = Math.max(dp[3],dp[2]-prices[i])
    let val4 = Math.max(dp[4],dp[3]+prices[i])
    dp = [val0,val1,val2,val3,val4]
  }
  return dp[4]
};

买卖股票最佳时机（188）

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/description/

图 3

思路
至多可以买卖k次
从前面一道题可以看出规律，dp[i][k]的状态由dp[i-1][k]和dp[i-1][k-1]决定

  • 1、dp[i][j],(0<i<n;0<j<2*k),表示第i天的2k种状态，
  • 2、递推公式，dp[i][j]
    • j是奇数，持有状态：max(dp[i-1][j],dp[i-1][j-1]-prices[i])
    • j是偶数，不持有状态：max(dp[i-1][j],dp[i-1[j]+prices[i]])
  • 3、初始化，索引为奇数的元素全部初始化为-prices[0],其余全为0
  • 4、遍历，从前往后
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var maxProfit = function(k, prices) {
  let n = prices.length
  let dp = Array(2*k+1).fill(0)
  for (let i=1;i<2*k;i+=2){
    dp[i] = -prices[0]
  }
  for(let i=1;i<n;i++){
    let arr =[0]
    for (let j=1;j<=2*k;j++){
      if(j%2 === 1) arr.push(Math.max(dp[j],dp[j-1]-prices[i]))
      else arr.push(Math.max(dp[j], dp[j - 1] + prices[i]))
    }
    dp = arr
  }
  return dp[2*k]
};

买卖股票的最佳时机含冷冻期(309)

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/

图 4

思路

  • 1、dp[j]表示当天股票状态，
    • dp[0] 表示持有股票
    • dp[1] 表示保持卖出股票的状态
    • dp[2] 表示当天卖出股票的操作
    • dp[3] 冷冻的期
  • 2、递推公式
    • dp[0] = max(dp[0],dp[3]-prices[i],dp[1]-prices[i])
    • dp[1] = max(dp[1],dp[3])
    • dp[2] = dp[0]+prices[i]
    • dp[3] = dp[2]
  • 3、初始化
    • dp[0] = -prices[i]
    • dp[1] = 0
    • dp[2] = 0
    • dp[3] = 0
  • 4、遍历顺序
    结果取最后一天状态1，2，3的最大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
var maxProfit = function(prices) {
  let n = prices.length
  let dp = Array(4).fill(0)
  dp[0] = -prices[0]
  for(let i=0;i<n;i++){
    let val0 = Math.max(dp[0],dp[3]-prices[i],dp[1]-prices[i])
    let val1 = Math.max(dp[1],dp[3])
    let val2 = dp[0]+prices[i]
    let val3 = dp[2]
    dp = [val0,val1,val2,val3]
  }
  return Math.max(dp[1],dp[2],dp[3])
};

买卖股票的最佳时机含手续费(714)

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/

图 5

思路

  • 1、dp[j]表示每天的状态
    • dp[0] 持有
    • dp[1] 不持有
  • 2、递推公式
    • dp[0] = max(dp[0],dp[1]-price[i]-fee) ,保持前一天的持有状态，或者在前一天不持有的状态下买入
    • dp[1] = max(dp[1],dp[0]+prices[i]),保持前一天不持有的状态，或者在昨天持有股票的基础上卖出股票
  • 3、初始化
    • dp[0] = -prices[0]-fee
    • dp[1] = 0
  • 4、遍历
1
2
3
4
5
6
7
8
9
10
11
12
var maxProfit = function(prices, fee) {
  let n = prices.length
  let dp = Array(2).fill(0)
  dp[0] = -prices[0]- fee
  dp[1] = 0
  for(let i=0;i<n;i++){
    let val0 = Math.max(dp[0],dp[1]-prices[i]-fee)
    let val1 = Math.max(dp[1],dp[0]+prices[i])
    dp = [val0,val1]
  }
  return dp[1]
};