Grokking 243-2

class Solution {
    int helper(int[][] costs, int i, int j, int[][] memo) {
        if (i + j >= costs.length) {
            return 0;
        }

        if (memo[i][j] != 0) {
            return memo[i][j];
        }

        memo[i][j] = Integer.MAX_VALUE;
        if (i >= costs.length / 2) {
            memo[i][j] = costs[i + j][1] + helper(costs, i, j + 1, memo);
        } else if (j >= costs.length / 2) {
            memo[i][j] = costs[i + j][0] + helper(costs, i + 1, j, memo);
        } else {
            memo[i][j] = Math.min(costs[i + j][0] + helper(costs, i + 1, j, memo),
                           costs[i + j][1] + helper(costs, i, j + 1, memo));
        }
        return memo[i][j];
    }

    public int twoCitySchedCost(int[][] costs) {
        int[][] memo = new int[costs.length][costs.length];
        return helper(costs, 0, 0, memo);
    }
}