代码随想录算法训练营|day48
121.买卖股票的最佳时机
本题中股票只能买卖一次
dp[i][0] 表示第i天不买入股票
持有的最大现金;dp[i][1] 表示第i天买入股票
持有的最大现金。
不买股票持有的最大现金 | 买入股票持有的最大现金 |
---|---|
前一天为未买入状态 dp[i-1][0] 前一天为买入状态,今天卖出 dp[i-1][1]+prices[i] | 前一天为买入状态 dp[i-1][1] 今天为买入状态 -prices[i] |
func maxProfit(prices []int) int {
if len(prices) == 0 {
return 0
}
dp := make([][]int, len(prices))
for i := 0; i < len(prices); i++ {
dp[i] = make([]int, 2)
}
dp[0][0] = 0
dp[0][1] = -prices[0]
for i := 1; i < len(prices); i++ {
dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
dp[i][1] = max(dp[i-1][1], -prices[i])
}
return dp[len(prices) - 1][0]
}
空间优化:可以看到第i天状态只依赖于第i-1天的状态,因此只需要记录前一天状态即可
func maxProfit(prices []int) int {
if len(prices) == 0 {
return 0
}
dp0, dp1 := 0, -prices[0]
for i := 1; i < len(prices); i++ {
dp0 = max(dp0, dp1+prices[i])
dp1 = max(dp1, -prices[i])
}
return dp0
}
贪心:在历史最低点买入,最高点卖出
func maxProfit(prices []int) int {
if len(prices) == 0 {
return 0
}
minPrice := prices[0]
res := 0
for i := 1; i < len(prices); i++ {
if prices[i] < minPrice {
minPrice = prices[i]
}
res = max(res, prices[i]-minPrice)
}
return res
}
122.买卖股票的最佳时机II
较上题多了条件:股票可以进行多次买卖
dp[i][0] 表示第i天不买入股票
持有的最大现金;dp[i][1] 表示第i天买入股票
持有的最大现金。
所以在当天是买入状态时,持有的最大现金为前一天买入状态持有的最大现金
和前一天卖出今天买入后持有的最大现金
的最大值
func maxProfit(prices []int) int {
if len(prices) == 0 || len(prices) == 1 {
return 0
}
dp := make([][]int, len(prices))
for i := 0; i < len(prices); i++ {
dp[i] = make([]int, 2)
}
dp[0][0] = 0
dp[0][1] = -prices[0]
for i := 1; i < len(prices); i++ {
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])
}
return dp[len(prices)-1][0]
}
空间优化
func maxProfit(prices []int) int {
if len(prices) == 0 || len(prices) == 1 {
return 0
}
dp0, dp1 := 0, -prices[0]
for i := 0; i < len(prices); i++ {
dp0 = max(dp0, dp1+prices[i])
dp1 = max(dp1, dp0-prices[i])
}
return dp0
}
贪心:只加正数
因为不限制交易次数,故只要今天股价比昨天高,就交易。
func maxProfit(prices []int) int {
if len(prices) == 0 || len(prices) == 1 {
return 0
}
sum := 0
for i := 1; i < len(prices); i++ {
if prices[i] > prices[i-1] {
sum += prices[i] - prices[i-1]
}
}
return sum
}
代码随想录文章详解
原文地址:https://blog.csdn.net/weixin_43785190/article/details/136412529
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!