educative.io

Two city scheduling 1029 in Leetcode

Courses
,
#1

Hi,
Here is a leetcode problem 1029 - tagged easy. Seemed like a straightforward application of Top down DP. I did the brute force and worked for smaller test cases. Good.

So, moved on to top down DP and here is my solution. It does not work for a few cases. Any ideas why ?

I came up with this top-down approach. And realized it does not work for a few test cases. Any ideas why ?

class Solution {
    int n;

    public int twoCitySchedCost(int[][] costs) {
        this.n = costs.length / 2;
        //System.out.println(" number of cities total = " + n*2);

        boolean[] visited = new boolean[2*n+1];
        Integer[][] dp = new Integer[1+n][1+n];

        return helper(costs, 2*n, n, n, dp);
        
    }
    private int helper(int[][] costs, 
                        int indx, int city1Cnt,int city2Cnt, 
                        Integer[][] dp){
        //System.out.println(" indx = " + indx);
        //System.out.println(" city1Cnt = " + city1Cnt);
        //System.out.println(" city2Cnt = " + city2Cnt);
            
        if (indx < 0 || city1Cnt < 0 || city2Cnt < 0 )
            return 2000;
        
        if (city1Cnt == 0 && city2Cnt == 0)
            return 0;
        
        if (dp[city1Cnt][city2Cnt] == null){
            dp[city1Cnt][city2Cnt] = Math.min(costs[indx-1][0] + helper(costs,indx-1,city1Cnt-1,city2Cnt,dp),costs[indx-1][1] + helper(costs,indx-1,city1Cnt,city2Cnt-1,dp));
        }
        //System.out.println("About to return for city1Cnt = " + city1Cnt + " city2Cnt = " + city2Cnt + " $ " + dp[city1Cnt][city2Cnt]);
        return dp[city1Cnt][city2Cnt];
    }
}