DP #188 Best Time to Buy and Sell Stock IV

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

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

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

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