122.买卖股票的最佳时机-ii

dfs(i, hold) return int 如果要持有股票, 则最大利润为max(dfs(i-1, 1), dfs(i-1, 0) - prices[i]) 如果要不持有股票, 则最大利润为max(dfs(i-1, 0), dfs(i-1, 0) + prices[i])

class Solution {
    int[][] m;
    /**
     * dfs(i, hold) return int
     * 如果要持有股票, 则最大利润为max(dfs(i-1, 1), dfs(i-1, 0) - prices[i])
     * 如果要不持有股票, 则最大利润为max(dfs(i-1, 0), dfs(i-1, 0) + prices[i])
     */
    public int maxProfit(int[] prices) {
        int len = prices.length;
        m = new int[len][2];
        for (int[] row : m) {
            Arrays.fill(row, Integer.MIN_VALUE);
        }
        return dfs(prices, prices.length-1, 0);
    }

    // [0] 持股的时候的最大利润, [1] 没有持股的时候的最大利润
    private int dfs(int[] prices, int i, int hold) {
        if (i < 0) {
            return hold == 0
                    ? 0
                    : Integer.MIN_VALUE / 2;
        }
        if (m[i][hold] != Integer.MIN_VALUE) {
            return m[i][hold];
        }

        if (hold == 1) {
            return m[i][hold] = Math.max(dfs(prices, i-1, 0) - prices[i], dfs(prices, i-1, hold));
        }
        return m[i][hold] = Math.max(dfs(prices, i-1, 1) + prices[i], dfs(prices, i-1, hold));

    }
}