DP - Visualization of the Algorithm and Code for Count Square Submatrices with All Ones
** DP (Dynamic Programming)\n\nThinking: The dp[i][j] will represent the length of the square in the bottom\n          right corner.\n\n  If the value of any ce
** DP (Dynamic Programming)**\n\nThinking: The dp[i][j] will represent the length of the square in the bottom\n          right corner.\n\n  If the value of any cell is 1, then we compare it with it above, left and\n  diagonal up-left corners. The length of the square will be the minimum of\n  these 3 neighbors + 1, (+1 -> because if either of the neighbors are zero,\n  this cell is still a square with side 1). If any one of the neighbors are zero\n  that means the square is missing a side and hence it won\'t count towards\n  the length of the square.\n\n  Ex:\n\n      0 1 0\n      1 1 0\n      0 0 0\n\n  Let\'s say for cell in row 2, column 2, =>\n    left neighbor is 1, up neighbor is 1, but up diagonal is 0, hence\n    we cannot form a square of size 2. But we still can form a square of size 1\n    at row 2, column 2\n\n\n  The idea of dp[i][j] represents bottom right of the matrix[i][j], is so\n  that we can precompute the values and use it for reference when iterating over\n  other index. For any index we visit, we will have the neighbors value already\n  calculated.\n\n  For the top most row and left most column, the dp will be same as matrix,\n  because in top row - their up neighbor is missing, so min(left, above, diag)\n  will be zero. Similary in the left column, left is missing.\n\n  Ex: Our input matrix:\n\n\t  0 1 1 1\n\t  1 1 1 1\n\t  0 1 1 1\n\n  Hence initial dp will look like=>\n\n\t  0 1 1 1\n\t  1\n\t  0\n\n  Now, let\'s start iterating in matrix if value at index is 1, then we check\n  neighbors. If zero, then we just update dp[i][j] as zero.\n\n  For (1, 1) -> second column in third row, we find min of all neighbors,\n  i.e => left: 1, above: 1, diagonal up: 0, so 1 + min(all three) => 1\n\n\t  0 1 1 1\n\t  1 1\n\t  0\n\n  For (1, 2), => 1, left: 1, top: 1, diagonalup: 1, so a square can be formed\n  with length 2, as all present and min (1, 1, 1) is 1, + 1 => 2\n\n\t  0 1 1 1\n\t  1 1 2\n\t  0\n\n  For (1, 3) => again: left: 1, top: 1, diagonalup: 1, min(1, 1, 1) + 1 => 2\n\n\t  0 1 1 1\n\t  1 1 2 2\n\t  0\n\n  For(2, 1) => left is zero, top: 1, diagonalup: 1, so min(0, 1, 1) + 1 => 1\n\n\t  0 1 1 1\n\t  1 1 2 2\n\t  0 1\n\n  For(2, 2) => left: 1, top: 2, diagonalup: 1, so min(1, 1, 1) + 1 => 2\n\n\t  0 1 1 1\n\t  1 1 2 2\n\t  0 1 2\n\n  For(2, 3) => left: 2, top: 2, diagonalup: 2, so min(2, 2, 2) + 1 => 3\n\n\t  0 1 1 1\n\t  1 1 2 2\n\t  0 1 2 3\n\nThere we go, we are done!!\n\n**Java Code**\n```\npublic int countSquares(int[][] matrix) {\n    /*\n      Time Complexity: O(MN)\n      Space Complexity: O(1) input array is modified\n    */\n\n    int result = 0;\n\n    for(int i = 0; i < matrix.length; i++) {\n      for(int j = 0; j < matrix[0].length; j++) {\n\n        // for top most row(i == 0) and left most column j == 0, directly\n        // value in the matrix will be added as result.\n        if(matrix[i][j] > 0 && i > 0 && j > 0) {\n          int min = Math.min(matrix[i-1][j], Math.min(matrix[i][j-1], matrix[i-1][j-1]));\n          matrix[i][j] = min + 1;\n        }\n\n        result += matrix[i][j];\n      }\n    }\n\n    return result;\n  }
['Dynamic Programming', 'Java']