买卖股票的最佳时机 II

买卖股票的最佳时机 II

leetcode 链接

思路：

1. dp[i][j] 第 i 天时的状态，j 为 0 表示未持有股票，1 表示持有股票
2. 初始化 dp 数组，dp[0][0] = 0, dp[0][1] = -prices[0]
3. 确定遍历方向，从前往后遍历
4. 确定转移方程，dp[i][0] = Math.max(dp[i - 1][1] + prices[i], dp[i - 1][0]), dp[i][1] = Math.max(dp[i - 1][0] - prices[i], dp[i - 1][1])
5. 返回 dp[prices.length - 1][0]

typescript 解法

function maxProfit(prices: number[]): number {
  // dp[0][j] 表示第j天未持有股票的收益
  // dp[1][j] 表示第j天持有股票的收益
  let dp = Array.from({ length: 2 }, () => new Array(prices.length).fill(0));

  dp[0][0] = 0;
  dp[1][0] = -prices[0];

  for (let i = 1; i < prices.length; i++) {
    dp[0][i] = Math.max(dp[1][i - 1] + prices[i], dp[0][i - 1]);
    dp[1][i] = Math.max(dp[0][i - 1] - prices[i], dp[1][i - 1]);
  }
  return dp[0][prices.length - 1];
}

go 解法

func maxProfit(prices []int) int {
    // dp[i][j] 第i天时的状态，j为0表示未持有股票，1表示持有股票
    lenP := len(prices)
    dp := make([][]int, lenP)
    for i := 0;i < lenP; i ++ {
        dp[i] = make([]int, 2)
    }
    dp[0][0] = 0
    dp[0][1] = -prices[0]

    for i := 1; i < lenP; i ++ {
        dp[i][0] = max(dp[i - 1][1] + prices[i], dp[i - 1][0])
        dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1])
    }
    return dp[lenP - 1][0]
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}