Best Time to Buy and Sell Stock

类似的股票问题
求在低价格买入股票，高价格卖出。每次卖出会产生交易费，求最优解
例如：
Input: prices = [1, 3, 2, 8,5, 4, 9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
• Buying at prices[0] = 1
• Selling at prices[3] = 8
• Buying at prices[5] = 4
• Selling at prices[6] = 9The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

自底向上dp

    public int profit(int[] prices, int fee){
        int n = prices.length;
        int[] hold = new int[n];
        int[] unhold = new int[n];
        hold[0] = -prices[0];
        for (int i = 1; i < n; i++) {
            hold[i] = Math.max(hold[i - 1], unhold[i-1] - prices[i]);
            unhold[i] = Math.max(unhold[i - 1], hold[i - 1] - fee + prices[i]);
        }
        return unhold[n - 1];
    }