1 买卖股票的最佳时机 I （只买卖一次）
问题描述
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
思路：
1 暴力解法：循环遍历两次，记录买入和卖出的差值，取最大值
2 贪心算法；只遍历一次，记录波谷，当到达波峰时，记录差值，最后保留最大值。
3 动态规划：
（1）：确定dp
dp[i][0]: 第i天持有股票，此时手里的最大金钱
dp[i][1]: 第i天不持有股票，此时手里的最大金钱
（2）：状态变化规则
dp[i][0] = max(dp[i-1][0],-price[i]) // 其实这里要保证买入时股票价格尽可能小，而加了负号，所以去最大值
dp[i][1] = max(dp[i-1][0]+price[i], dp[i-1][1])
(3)初始化
dp[0][0] = -price[0]
dp[0][0] = 0
(4) 顺序：
从前往后
（5）举例子
。。。。
go语言实现
func maxProfit(prices []int) int {
//暴力
// res := 0
// for i:=0; i<len(prices)-1;i++ {
// for j:=i+1; j<len(prices);j++{
// if (prices[j]-prices[i]) >res {
// res = prices[j]- prices[i]
// }
// }
// }
// return res
// 贪心
// m := prices[0]
// for i:=1; i<len(prices); i++ {
// if prices[i]>m {
// if (prices[i]-m)>res {
// res = prices[i] -m
// }
// } else {
// m = prices[i]
// }
// }
// return res
//动态规划
length := len(prices)
dp := make([][]int,length)
for i:=0;i<length;i++ {
dp[i] = make([]int,2)
}
dp[0][0] = -prices[0]
dp[0][1] = 0
for i:=1;i<length;i++ {
dp[i][0] = max(dp[i-1][0],-prices[i])
dp[i][1] = max(dp[i-1][0]+prices[i], dp[i-1][1])
}
return dp[length-1][1]
}
func max(a,b int) int{
if a>b { return a}
return b
}
买卖股票的最佳时机II (可以买卖多次）
问题描述
给定一个数组 prices ，其中 prices[i] 表示股票第 i 天的价格。
在每一天，你可能会决定购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以购买它，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
思路
和上一个的动态规划思路基本一致：
不同：
买卖一次：
-price[i] :只买卖一次，很好理解。
dp[i][0] = max(dp[i-1][0],-price[i])
卖买多次：
dp[i-1][1] - price[i] : 这个时通过上一次不持有股票的状态传递下来
dp[i][0] = max(dp[i-1][0],dp[i-1][1] - price[i])
go语言实现
func maxProfit(prices []int) int {
if len(prices) == 1{
return 0
}
length := len(prices)
dp := make([][]int,length)
for i:=0;i<length;i++ {
dp[i] = make([]int,2)
}
dp[0][0] = -prices[0] //持有股票
for i:=1;i<length;i++ {
dp[i][0] = max(dp[i-1][0],dp[i-1][1]-prices[i])
dp[i][1] = max(dp[i-1][0]+prices[i], dp[i-1][1])
}
return dp[length-1][1]
}
func max(a,b int) int{
if a>b { return a}
return b
}
买卖股票的最佳时机系列III (限定交易的次数）
问题描述
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）
思路
确定dp：
不管有多少个股票，我们针对一个股票有以下几种状态：
dp[i][0] : 不操作
dp[i][1] : 第一次持有股票 ，手里最大金额
dp[i][2] : 第一次 将持有股票卖出，手里最大金额
dp[i][3] : 第二次持有股票，手里最大金额
dp[i][4] : 第二次将持有股票卖出，手里最大金额
遍历所有股票，更新上述的状态，
状态变化规则：
dp[i][0] = dp[i-1][0] //不变
//1 上一次持有股票 2 上一次不持有股票 - 当前股票的价值，比较1 2大小
dp[i][1] = max( dp[i-1][1], dp[i-1][0] -price[i] )
//1 上一次不持有股票 2 上一次持有股票 + 当前股票的价值，比较1 2大小
dp[i][2] = max( dp[i-1][2] , dp[i-1][1]+price[i] )
//和上面类似
dp[i][3] = max( dp[i-1][3] , dp[i-1][2]- price[i] )
dp[i][4] = max( dp[i-1][4] , dp[i-1][3]+price[i] )
初始化
此时只有一个股票
dp[0][0] =0
dp[0][1] = -price[0]
dp[0][2] =0
dp[0][3] = -price[0]
dp[0][4] =0
遍历的顺序：
从前往后
举例
。。。。
go语言实现
func maxProfit(prices []int) int {
dp:=make([][]int,len(prices))
for i:=0;i<len(prices);i++{
dp[i]=make([]int,5)
}
dp[0][0]=0
dp[0][1]=-prices[0]
dp[0][2]=0
dp[0][3]=-prices[0]
dp[0][4]=0
for i:=1;i<len(prices);i++{
dp[i][0]=dp[i-1][0]
dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])
dp[i][2]=max(dp[i-1][2],dp[i-1][1]+prices[i])
dp[i][3]=max(dp[i-1][3],dp[i-1][2]-prices[i])
dp[i][4]=max(dp[i-1][4],dp[i-1][3]+prices[i])
}
return dp[len(prices)-1][4]
}
func max(a,b int)int{
if a>b{
return a
}
return b
}
买卖股票的最佳时机IV (限定交易的次数为K）
问题描述
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
思路
和上述的思路一样，只是把 2 换成了 K
归纳总结。
go语言实现
func maxProfit(k int, prices []int) int {
if len(prices)==0 || k==0 {
return 0
}
dp:=make([][]int,len(prices))
for i:=0;i<len(prices);i++{
dp[i]=make([]int,2*k+1)
}
for i := 0 ; i<2*k+1 ; i++ {
if i%2==0 {
dp[0][i] = 0
} else {
dp[0][i] = -prices[0]
}
}
for i:=1;i<len(prices);i++{
dp[i][0] = dp[i-1][0]
for j :=1;j <2*k+1; j++ {
if j%2 == 0 {
dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]+prices[i])
} else {
dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]-prices[i])
}
}
}
//fmt.Println(dp)
return dp[len(prices)-1][2*k]
}
func max(a,b int)int{
if a>b{
return a
}
return b
}
买卖股票的最佳时机含冷冻期（冷冻期）
问题描述
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
思路：
状态：
1 持有股票
2 不持有股票，但是度过了冷冻期
3 今天卖出股票，
4 不持有股票，为冷冻期
没遍历一次股票，更新状态：
go语言实现
func maxProfit(prices []int) int {
length := len(prices)
res := make([][]int,length)
for i:=0; i<len(res) ;i++{
res[i]= make([]int,4)
}
res[0][0]= -prices[0]
for i:=1;i<len(res);i++{
//持有股票的状态
//1 昨天也持有股票 2 昨天不持有股，已经度过冷冻 3 昨天是冷冻期，今天就不是了 ，比较 1 2 3 的大小
res[i][0] = max(res[i-1][0],max(res[i-1][1]-prices[i],res[i-1][3]-prices[i]))
//已经度过冷冻期，不持有股票
//等价于：1 昨天度过冷冻期，不持有股，2 昨天为冷冻期 。两者最大值。
res[i][1] = max(res[i-1][1],res[i-1][3])
res[i][2] = res[i-1][0] + prices[i] //今天卖出股票 ：等价于昨天持有股票，今天卖出
res[i][3] = res[i-1][2] //今天是冷冻期，所以等价于昨天卖出
}
return max(res[length-1][1],max(res[length-1][2],res[length-1][3]))
}
func max(a,b int) int{
if a>b { return a}
return b
}
