代码如下
func maxProfit(prices []int) int { //建立一个二维数组 dp[i][0]表示持有股票的最大金钱 dp[i][1] 表示不持有股票的最大金钱
dp := make([][]int,len(prices))
for i,_ := range dp {
dp[i] = make([]int,2)
}
dp[0][0] = -prices[0] // 第0天持有股票，则必须买入股票
dp[0][1] = 0 //第0天不持有股票，则什么都不做，金额为0
for i := 1 ; i < len(prices) ; i++ {
dp[i][0] = max(dp[i-1][0],-prices[i]) //如果在第i天持有股票，那么就有两种可能，一种是前一天持有股票，而今天什么都不做，那么他的金钱就是dp[i-1][0]，或者是之前不持有，在第i天持有，那么金钱就是-prices[i] ，那么在这一天持有股票的最大值是两者的最大值
dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i]) //如果在第i天不持有股票，同样有两种可能，一种是前一天就不持有股票，今天什么都没做，还有一种就是前一天是持有股票，今天把股票卖了出去
}
return max(dp[len(prices)-1][0],dp[len(prices)-1][1])
}
func max(a,b int) int {
if a > b {
return a
}else {
return b
}
}
122 买卖股票的最佳时机二
代码如下
func maxProfit(prices []int) int {
dp := make([][]int,len(prices))
for i,_ := range dp {
dp[i] = make([]int,2)
}
dp[0][0] = -prices[0]
dp[0][1] = 0
for i := 1 ; i < len(prices) ; i++ {
dp[i][0] = max(dp[i-1][0],dp[i-1][1]-prices[i]) 和上面唯一区别是，如果在第i天想要买入股票，那么金额应该是前一天不持有股票的金额减去今天这支股票的金额
dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i])
}
return max(dp[len(prices)-1][0],dp[len(prices)-1][1])
}
func max(a,b int) int {
if a > b {
return a
}else {
return b
}
}
123 买卖股票的最佳时机3
代码如下
func maxProfit(prices []int) int {
dp := make([][]int,len(prices))
for i ,_ := range dp {
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] //如果第i天不操作，那么该与i-1天的值相同
dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i]) // 如果第i天不进行买入操作，那么其结果等于第i-1天，如果进行买入操作，则相当于前一天不操作，第i天买入这支股票
dp[i][2] = max(dp[i-1][2],dp[i-1][1]+prices[i]) // 如果第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 max(dp[len(prices)-1][2],dp[len(prices)-1][4]) //因为至多为2次，可能包含第二次怎么买都是亏得情况。所以比较卖出一次和两次的最大值
}
func max(a,b int) int {
if a > b {
return a
}else {
return b
}
}
