Java DP Easy to understand solution ttt
Dynamic Programming\nWe will be using a 2D matrix of size M * N. Each cell of the dp matrix,  dp[i][j]  will store the number of square submatrices with the bot
**Dynamic Programming**\nWe will be using a 2D matrix of size M * N. Each cell of the dp matrix,  **dp[i][j]  will store the number of square submatrices with the bottom most cell at dp[i][j]**.\n\nLet\'s see a few examples:\nm = 3, n=3;\n[ 0 1 1 1]\n[1 1 1 1]\n[0 1 1 1]\n\n```\nIn the first row we can have square matrices of size 1 only, so in our dp[][] matrix we can simply add 1 if we have 1 in out original matrix, Similarly for the first coloumn where only square matrices of size 1 are possible.\n\nhence, \nwhen(FIRST ROW || FIRST COLUMN) dp[i][j] = matrix[i][j]\n\nFor the rest of the cells, we need to worry about it ONLY if matrix has a 1 in the same cell position. If not simply put 0. If it is a 1, the following cases can arise:\n* CASE 1: The cell is a square submatrix independently of size 1, iff dp[i-1][j], dp[i][j-1] and dp[i-1][j-1] are not all greater than 1. Because if any one of them is 0, it means they dont form a sqaure submatrix and hence cannot form a larger submatrix. \n* CASE 2: All three cells of dp[][], namely top left diagonall, top, and left are at least 1, it means the curr cell can form a larger submatrix. to find out how many such submatrices will be formed, we can simply use the formula dp[i][j] = Math.min( top-left-diagonal-cell, Math.min(top, left)) + 1;   // +1 as it can form a square submatrix of size 1 by itself\n\n\nOnce, we have populated all the cell, we can simply add all the cell values to get the total no of submatrices\n\nEach cell of dp contains the number of sqaure submatrices upto that cell, so we simply need to add all cell data to get total submatrices\n```\n\n**CODE**\n\n```\nclass Solution {\n    public int countSquares(int[][] matrix) {\n        int row = matrix.length;\n        int col = matrix[0].length;\n        int sum = 0;             //to keep track of all cell data as we populate the dp\n        int[][] dp = new int[row][col];\n        for(int i = 0; i<row; i++){\n            for(int j = 0; j<col; j++){\n                if(i==0 || j==0){                           // as explained above for first row and first column\n                    dp[i][j] = matrix[i][j];\n                }\n                else if(matrix[i][j] == 1){\n                     if(dp[i-1][j-1]>=1 && dp[i][j-1]>=1 && dp[i-1][j]>=1){\n                         dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i][j-1], dp[i-1][j])) + 1;\n                     }else{\n                         dp[i][j] = 1;\n                     }\n                }\n\t\t\t\tsum += dp[i][j];               // adding the cell data to sum \n            }\n        }\n        return sum;\n    }\n}\n```\n\n
['Dynamic Programming', 'Java']