LeetCode 714. 买卖股票的最佳时机含手续费

题目：

LeetCode 714. 买卖股票的最佳时机含手续费

题解：动态规划

定义二维数组dp[n][2]:

• dp[i][0] 表示第 i 天不持有股票可获得最大利润
• dp[i][1] 表示第 i 天持有股票可获得最大利润

定义状态转移方程：

不持有：dp[i][0] = max(dp[i-1][0], dp[i-1][1]+price[i]-fee)

今天不持有，可以从两个状态推演出来：
1.昨天也不持有

2.昨天持有，然后卖了

持有：dp[i][1] = max(dp[i-1][1], dp[i-1][0] - price[i])

今天持有，可以从两个状态推演出来：

1.昨天就持有

2.昨天不持有，今天买了新的股票

初始值：

不持有：dp[0][0] = 0

持有：dp[0][1] = -price[0]

public int maxProfit(int[] prices, int fee) {
    int[][] dp = new int[prices.length][2];
    dp[0][0] = 0;
    dp[0][1] = -prices[0];

    for (int i = 1; i < prices.length; i++) {
        dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i] - fee);
        dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
    }

    return dp[prices.length-1][0];
}

时间复杂度：O(n)