DP #309 Best Time to Buy and Sell Stock with Cooldown

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, n, dp);
        return tabOpt(prices, n);
    }

    // Space optimised Tabulation solution
    public int tabOpt(int[] pr, int n) {
        int[] dp = new int[2];
        int[] dpa = 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) {
                    cur[b] = Math.max(-pr[i] + dp[1 - b], dp[b]);
                } else {
                    if (i + 2 >= n)
                        cur[b] = Math.max(pr[i], dp[b]);
                    else
                        cur[b] = Math.max(pr[i] + dpa[1 - b], dp[b]);
                }
            }
            dpa = dp;
            dp=cur;

        }
        return dp[1];
    }

    // Tabulation solution
    public int tab(int[] pr, int n) {
        int[][] dp = new int[n + 2][2];
        for (int i = n - 1; i >= 0; i--) {
            for (int b = 1; b >= 0; b--) {
                if (b == 1) {
                    dp[i][b] = Math.max(-pr[i] + dp[i + 1][1 - b], dp[i + 1][b]);
                } else {
                    dp[i][b] = Math.max(pr[i] + dp[i + 2][1 - b], dp[i + 1][b]);
                }
            }
        }
        return dp[0][1];
    }

    // Recursive solution
    public int recur(int i, int b, int[] pr, int n, int[][] dp) {
        if (i >= n)
            return 0;

        if (dp[i][b] != -1)
            return dp[i][b];
        if (b == 1) {
            int prb = -pr[i] + recur(i + 1, 1 - b, pr, n, dp);
            int prnb = recur(i + 1, b, pr, n, dp);
            return dp[i][b] = Math.max(prb, prnb);
        } else {
            int prs = pr[i] + recur(i + 2, 1 - b, pr, n, dp);
            int prns = recur(i + 1, b, pr, n, dp);
            return dp[i][b] = Math.max(prs, prns);
        }
    }
}