1029.txt

class Solution {
    int dp[][][];
    public int twoCitySchedCost(int[][] A) {
        dp=new int[A.length][A.length/2+1][A.length/2+1];
        for(int i=0;i<dp.length;i++){
            for(int j=0;j<dp[0].length;j++){
                Arrays.fill(dp[i][j],-1);
            }
        }
        return dfs(A,0,A.length/2,A.length/2); 
    }
    
    public int dfs(int A[][],int i,int a,int b){
        if(i>=A.length)return 0;
        if(dp[i][a][b]!=-1)return dp[i][a][b];
        int acost=A[i][0];
        int bcost=A[i][1];
        
        int res=Integer.MAX_VALUE;
        if(a>0){
            res=Math.min(res,acost+dfs(A,i+1,a-1,b));
        }
        if(b>0){
            res=Math.min(res,bcost+dfs(A,i+1,a,b-1)); 
        }
        dp[i][a][b]=res;
        return res;
    }
}


class Solution {
    public int twoCitySchedCost(int[][] A) {
        Arrays.sort(A,(a,b)->{
            return Math.abs(b[0]-b[1])-Math.abs(a[0]-a[1]);
        });
        int a=A.length/2;
        int b=a;
        int res=0;
        for(int i=0;i<A.length;i++){
            if(A[i][0]<A[i][1]){
                if(a>0){
                    res+=A[i][0];a--;  
                }else{
                    res+=A[i][1];b--;
                }
            }else{
                if(b>0){
                    res+=A[i][1];b--;
                }else{
                    res+=A[i][0];a--;
                }
            }
        }
        
        return res;
    }
}