DP - 2:Maximum Square Matrix With All Zeros

// public class Solution {

//     public static int minCostPath(int input[][]) {
//       
//         return minCostPath(input,0,0);
//     }
//     public static int minCostPath(int input[][],int i,int j) {
//         int m=input.length;
//         int n=input[0].length;
//         if(i==m-1 && j==n-1)
//             return input[i][j];
//         if(i>=m || j>=n)
//             return Integer.MAX_VALUE;
//         int x=minCostPath( input, i, j+1);
//         int y=minCostPath( input, i+1, j);
//         int z=minCostPath( input, i+1, j+1);
//         return input[i][j]+Math.min(Math.min(x,y),z);


//     }
// }



//memoization///////
// public class Solution {

// 	public static int minCostPath(int input[][]) {
// 	int output[][]=new int[input.length][input[0].length];
//         for(int i=0;i<output.length;i++)
//         {
//             for(int j=0;j<output[i].length;j++)
//             {
//                 output[i][j]=-1;
//             }
//         }
//         return helper(output,0,0,input);
//         }
//     private static int helper(int output[][],int i,int j,int input[][]){
//         int m=output.length;
//         int n=output[0].length;
//         if(i==m-1 && j==n-1)
//         {
//             output[i][j]=input[i][j];
//             return output[i][j];
//         }
//         if(i>=m || j>=n)
//         {
//             return Integer.MAX_VALUE;
//         }
//         if(output[i][j]!=-1)
//             return output[i][j];
//         int x=helper( output, i, j+1,input);
//         int y=helper( output, i+1, j,input);
//         int z=helper( output, i+1, j+1,input);
//         output[i][j]= input[i][j]+Math.min(Math.min(x,y),z);

//         return output[i][j];


//     }
// }

////////////////dp////////////////
public class Solution 
{
    public static int minCostPath(int input[][])
    {
        int m=input.length;
        int n=input[0].length;
        int storage[][]=new int[m][n];
        storage[m-1][n-1]=input[m-1][n-1];
        for(int i=m-2;i>=0;i--)
        {
            storage[i][n-1]=input[i][n-1]+storage[i+1][n-1];
        }
        for(int j=n-2;j>=0;j--)
        {
            storage[m-1][j]= storage[m-1][j+1]+input[m-1][j];
        }
        for(int i=m-2;i>=0;i--)
        {
            for(int j=n-2;j>=0;j--)
            {
                storage[i][j]=input[i][j]+Math.min(storage[i+1][j+1],Math.min(storage[i][j+1],storage[i+1][j]));
            } 
        }
        return storage[0][0];





    } 

}