121. 买卖股票的最佳时机 🌟🌟
力扣链接 🌟🌟
题目描述
给定一个数组 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。
解题思路
暴力方法：两层 for 循环 贪心法：取最左侧最小价格，取右边最大值，计算最大利润
var maxProfit = function (prices) {
let lowerPrice = prices[0]
let profit = 0
for (let i = 0; i < prices.length; i++) {
lowerPrice = Math.min(lowerPrice, prices[i])
profit = Math.max(profit, prices[i] - lowerPrice)
}
return profit
}
某些股票买卖具体场景下可以使用贪心或其他思路解决，但动态规划是解决这一系列的题目的通用方法
动规五部曲：
确定 dp 数组及下标的含义
每天有两种状态：
- 持有这只股股票所得的最多现金
- 不持有这只股股票所得的最多现金
因此 dp 数组必须是个二维数组表示
dp[i][0]：表示第 i 天持有股票所得最多现金dp[i][1]：表示第 i 天不持有股票所得最多现金
“持有”不代表当天买入，也有可能昨天已经买入，今天保持持有的状态
确定递推公式
dp[i][0]即第 i 天持有股票可以由两个状态推出：dp[i-1][0]即第 i-1 天已经持有该股票，今天保持现状，所得现金- 第 i 天买入，所得现金就是今天买入股票后所得现金
0 - prices[i] = -prices[i]，初始现金为 0
dp[i][0]在两者中选最大的：`dp[i][0]` = Math.max(dp[i - 1][0], -prices[i])dp[i][1]即第 i 天不持有股票，也由两个状态推出来dp[i-1][1]即第 i-1 天不持有股票，今天保持现状，所得现金- 第 i 天卖出股票，所得现金为
dp[i-1][0] + prices[i]
`dp[i][1]` = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i])dp 数组初始化
从递推公式得出需要考虑
dp[i-1][0]和dp[i-1][1]，所以必须初始化dp[0][0]和 dp[0][1]dp[0][0] = -prices[0]，第 0 天持有股票，即买入，所得现金为 -prices[0]dp[0][1] = 0, 第 0 天不持有股票
确定遍历顺序
从前往后
举例推导 dp 数组
以 prices = [7,1,5,3,6,4] 为例，得到的 dp 数组为：
dp = [ [-7, 0], [-1, 0], [-1, 4], [-1, 4], [-1, 5], [-1, 5], ]
代码
var maxProfit = function (prices) {
const n = prices.length
const dp = new Array(n).fill().map(() => [0, 0])
dp[0][0] = -prices[0]
for (let i = 1; i < n; i++) {
// 第i天持有
dp[i][0] = Math.max(dp[i - 1][0], -prices[i])
// 第i天不持有
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i])
}
console.log(dp)
return Math.max(...dp[n - 1])
}
122.买卖股票的最佳时机 II 🌟🌟
力扣链接 🌟🌟
题目描述
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
- 示例 1:
- 输入: [7,1,5,3,6,4]
- 输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。 - 示例 2:
- 输入: [1,2,3,4,5]
- 输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。 - 示例 3:
- 输入: [7,6,4,3,1]
- 输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
- 1 <= prices.length <= 3 * 10 ^ 4
- 0 <= prices[i] <= 10 ^ 4
解题思路
prices[3] - prices[0]
= (prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])
所以只要今天比昨天高，就卖出 prices[i] - prices[i-1] > 0
动规五部曲：
确定 dp 数组及下标的含义
dp[i][0]表示第 i 天持有股票所得最多现金dp[i][1]表示第 i 天不持有股票所得最多现金
确定递推公式
股票可以买卖多次与只能买卖一次的区别在于：第 i 天买入时，现金可能不是 0
dp[i][0]即第 i 天持有股票的最大金额，可以由两个状态推出：dp[i - 1][0]即第 i-1 天持有股票的最大金额dp[i - 1][1] - prices[i]即第 i 天买入股票，所得最的金额
dp[i][0]在两者中选最大的：dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i])这里与买卖股票的最佳时机的区别是：
- 第 i 天买入股票，所得现金为
-prices[i]，即初始金额为 0，第一次买入 - 此处第 i 天买入股票，所得现金为
dp[i - 1][1] - prices[i]，初始金额为前一天不持有此股票的最大金额
dp 数组初始化
dp[0][0] = -prices[0]，第 0 天持有股票，即买入，所得现金为 -prices[0]dp[0][1] = 0，第 0 天不持有股票
确定遍历顺序
从前往后
举例推导 dp 数组
以 prices = [7,1,5,3,6,4] 为例，得到的 dp 数组为：
dp = [ [-7, 0], [0, 0], [0, 4], [2, 4], [2, 7], [3, 7], ]
代码
var maxProfit = function (prices) {
const n = prices.length
const dp = new Array(n).fill().map(() => [0, 0])
// 第0天持有股票
dp[0][0] = -prices[0]
dp[0][1] = 0
for (let i = 1; i < n; i++) {
// 第i天持有股票
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i])
// 第i天不持有股票
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i])
}
console.log(dp)
return Math.max(...dp[n - 1])
}
123.买卖股票的最佳时机 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 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
- 示例 3：
- 输入：prices = [7,6,4,3,1]
- 输出：0 解释：在这个情况下, 没有交易完成, 所以最大利润为 0。
- 示例 4：
- 输入：prices = [1] 输出：0
提示：
- 1 <= prices.length <= 10^5
- 0 <= prices[i] <= 10^5
解题思路
至多买卖两次，意味着可以买卖一次，买卖两次，也可以不买卖
一天可以有五种状态：
- 没有操作
- 第一次持有股票
- 第一次不持有股票
- 第二次持有股票
- 第二次不持有股票
动规五部曲：
确定 dp 数组及下标的含义
dp[i][j]中 i 表示第 i 天，j 表示五种状态[0-4]，所以dp[i][j]表示第 i 天状态 j 下所剩最大金额如：
dp[i][1]表示第 i 天持有股票的状态，并不是第 i 天一定买入，有可能第 i-1 天就买入了确定递归公式
达到
dp[i][1]状态有两种情况：- 第 i 天买入股票，那么
dp[i][1] = dp[i-1][0] - prices[i] - 第 i 天保持现状，沿用前一天买入股票的状态，即：
dp[i][1] = dp[i-1][1]
两者选择最大的：
dp[i][1] = Math.max(dp[i - 1][0] - prices[i], dp[i - 1][1])同理，达到
dp[i][2]状态有两种情况：- 第 i 天卖出股票，那么
dp[i][2] = dp[1 - 1][1] + prices[i] - 第 i 天保持现状，沿用前一天卖出股票的状态，即：
dp[i][2] = dp[i-1][2]
dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i])同理，达到
dp[i][3]和dp[i][4]也分别有两种情况：- 第 i 天买入/卖出
- 第 i 天保持现状，沿用前一天状态
dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]) dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i])- 第 i 天买入股票，那么
dp 数组初始化
dp[0][0] = 0，第 0 天不做操作，金额为 0dp[0][1] = -prices[0]，第 0 天第一次买入股票，金额为 -prices[0]dp[0][2] = 0，第 0 天第一次卖出股票，即当天买入当天卖出，金额为 0dp[0][3] = -prices[0]，第 0 天第二次买入股票，即第一次买入又卖出又重新买入，金额为 -prices[0]dp[0][4] = 0，第 0 天第二次卖出股票，即第一次买入又卖出又重新卖出，金额为 0
确定遍历顺序
从前往后
举例推导 dp 数组
以 prices = [1,2,3,4,5] 为例，得到的 dp 数组为：
dp = [ [0, -1, 0, -1, 0], [0, -1, 1, -1, 1], [0, -1, 2, -1, 2], [0, -1, 3, -1, 3], [0, -1, 4, -1, 4], ]
代码
var maxProfit = function (prices) {
const n = prices.length
const dp = new Array(n).fill().map(() => new Array(5).fill(0))
dp[0][1] = -prices[0]
dp[0][3] = -prices[0]
// j
// 1 第一次持有
// 2 第一次卖出
// 3 第二次持有
// 4 第二次卖出
for (let i = 1; i < n; i++) {
const price = prices[i]
dp[i][0] = dp[i - 1][0]
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - price)
dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + price)
dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - price)
dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + price)
}
console.log(dp)
return dp[n - 1][4]
}
京ICP备2022027737号
Copyright © 2022 - present @wangxiang