买卖股票的最好时机(二)

很容易想出这道题的状态转移方程

func MaxProfitBM81(prices []int) int {
    a, b := -prices[0], 0
    for i := 2; i <= len(prices); i++ {
        a, b = Max(a, b-prices[i-1]), Max(b, a+prices[i-1])
    }
    return b
}

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 计算最大收益
 * @param prices int整型一维数组 股票每一天的价格
 * @return int整型
*/
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,price:=range prices{
        if i==0{
            continue
        }
        dp[i][0]=max(dp[i-1][1]-price,dp[i-1][0])
        dp[i][1]=max(dp[i-1][0]+price,dp[i-1][1])
    }
    return max(dp[len(dp)-1][0],dp[len(dp)-1][1])
}

func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 计算最大收益
 * @param prices int整型一维数组 股票每一天的价格
 * @return int整型
*/
func maxProfit( prices []int ) int {
    // 动态规划
    if len(prices) < 2 {
        return 0
    }
    
    dp := make([][]int, len(prices))
    for i, _ := range dp {
        dp[i] = []int{0, 0}
    }
    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 max(x, y int) int {
    if x > y {
        return x 
    }
    return y
}