DP #122 Best Time to Buy and Sell Stock II

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        // int[][] dp = new int[n][2];
        // for (int[] r : dp)
        // Arrays.fill(r, -1);
        // return recur(0, 1, prices, dp);
        return tab(prices);
    }

    // Space optimised Tabulation solution
    public int tabOpt(int[] pr) {
        int n = pr.length;
        int[] dp = new int[2];

        for (int i = n - 1; i >= 0; i--) {
            int[] cur = new int[2];
            for (int b = 1; b >= 0; b--) {
                if (b == 1) {
                    int prb = -pr[i] + dp[1 - b];
                    int prnb = dp[b];
                    cur[b] = Math.max(prb, prnb);
                } else {
                    int prs = pr[i] + dp[1 - b];
                    int prns = dp[b];
                    cur[b] = Math.max(prs, prns);
                }
            }
            dp = cur;
        }

        return dp[1];
    }

    // Tabulation solution
    public int tab(int[] pr) {
        int n = pr.length;
        int[] dp = new int[2];
        dp[n][0] = dp[n][1] = 0;

        for (int i = n - 1; i >= 0; i--) {
            for (int b = 1; b >= 0; b--) {
                if (b == 1) {
                    int prb = -pr[i] + dp[i + 1][1 - b];
                    int prnb = dp[i + 1][b];
                    dp[i][b] = Math.max(prb, prnb);
                } else {
                    int prs = pr[i] + dp[i + 1][1 - b];
                    int prns = dp[i + 1][b];
                    dp[i][b] = Math.max(prs, prns);
                }
            }
        }

        return dp[0][1];
    }

    // Recursive solution
    public int recur(int i, int b, int[] pr, int[][] dp) {
        if (i == pr.length) {
            return 0;
        }
        if (dp[i][b] != -1)
            return dp[i][b];

        // can buy
        if (b == 1) {
            int prb = -pr[i] + recur(i + 1, 1 - b, pr, dp); // buy
            int prnb = recur(i + 1, b, pr, dp); // not buy
            return dp[i][b] = Math.max(prb, prnb);
        }
        // can sell
        else {
            int prs = pr[i] + recur(i + 1, 1 - b, pr, dp); // sell
            int prns = recur(i + 1, b, pr, dp); // not sell
            return dp[i][b] = Math.max(prs, prns);
        }
    }
}