122. 买卖股票的最佳时机 II

题意：

解题思路：

思路：
状态: dp[i][0]表示第i天不持有股票的最大收益，dp[i][1]表示第i天持有股票的最大收益。
状态转移方程:
1、前一天不持有股票; 或者前一天持有股票，今天卖出，取大的
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
2、前一天持有股票；或者前一天不持有股票，今天买入，取大的
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
初始化:
dp[0][0] = 0;dp[0][0]=0;dp[0][1] = -prices[0];
注意：买卖股票的最佳时机交易一次的区别，主要在状态转移方程上的差异,如下：
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
dp[i][1] = max(dp[i - 1][1], -prices[i]);

PHP代码实现：

class Solution {
    /**
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($prices) {
        if (empty($prices) || count($prices) == 0) return 0;
        $profit = 0;
        for($i = 1; $i < count($prices); $i++) {
            if ($prices[$i] > $prices[$i - 1]) {
                $profit += $prices[$i] - $prices[$i - 1];
            }
        }
        return $profit;
    }
    function maxProfitDp($prices) {
        if (empty($prices)) return 0;
        $dp = [];
        $dp[0][0] = 0;
        $dp[0][1] = -$prices[0];
        for ($i = 1; $i < count($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[count($prices)-1][0];
    }
    function maxProfit1($prices) {
        if (empty($prices) || count($prices) == 0) return 0;
        $profit = 0;
        $i = 0;
        $n = count($prices);
        while ($i < $n - 1) {
            //波谷
            while ($i < $n - 1 && $prices[$i+1] <= $prices[$i]) ++$i;
            $buyPrices = $prices[$i];
            //波峰
            while ($i < $n - 1 && $prices[$i+1] >= $prices[$i]) ++$i;
            $sellPrice = $prices[$i];
            $profit += ($sellPrice - $buyPrices);
        }
        return $profit;
    }
}

GO代码实现：

func maxProfit(prices []int) int {
    if len(prices) < 2 {
        return 0
    }
    dp := make([][2]int, len(prices))
    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][0] - prices[i], dp[i - 1][1])
    }
    return dp[len(prices) - 1][0]
}
func max(a, b int) int {
    if a > b {return a}
    return b
}
func maxProfit(prices []int) int {
    sum := 0
    for i := 1; i < len(prices); i++ {
        if prices[i] - prices[i - 1] > 0 {
            sum += prices[i] - prices[i - 1]
        }
    }
    return sum
}