Java - Recursive -> Memoization -> 2D Bottom Up -> 1D Bottom Up
\n- Each of the cells can be treated as the top left corner of a square submatrix\n\t- If the square has a length of \'x\'\n\t\t- Then we can generate \'x\' squ
```\n- Each of the cells can be treated as the top left corner of a square submatrix\n\t- If the square has a length of \'x\'\n\t\t- Then we can generate \'x\' square submatrices\n\t- This means we will need to find the length of the largest square with the top left corner at each \'row/col\'\n\t\t- How can we find the length of the largest square?\n\t\t\t- If we are currently at \'row/col\' and we have a value of 1 at the cell\n\t\t\t\t- We will need to find the largest square on the right, bottom and bottom right\n\t\t\t\t- Then we will take the minimum length of the three squares\n\t\t\t\t\t- We can increment the length by 1 to account for the current cell\n```\n```\npublic class CountSquareMatricesWithAllOnesRecursiveApproach {\n    public int countSquares(int[][] matrix) {\n        int squares = 0;\n\n        for (int row = 0; row < matrix.length; row++) {\n            for (int col = 0; col < matrix[row].length; col++) {\n                squares += getLength(row, col, matrix);\n            }\n        }\n\n        return squares;\n    }\n\n    private int getLength(int row, int col, int[][] matrix) {\n        if (row >= matrix.length || col >= matrix[row].length || matrix[row][col] == 0) return 0;\n\n        return Math.min(getLength(row + 1, col, matrix),\n                Math.min(getLength(row, col + 1, matrix), getLength(row + 1, col + 1, matrix))) + 1;\n    }\n}\n```\n```\npublic class CountSquareMatricesWithAllOnesMemoizationApproach {\n    public int countSquares(int[][] matrix) {\n        int[][] memo = new int[matrix.length][matrix[0].length];\n        int squares = 0;\n\n        for (int row = 0; row < matrix.length; row++) {\n            for (int col = 0; col < matrix[row].length; col++) {\n                squares += getLength(row, col, matrix, memo);\n            }\n        }\n\n        return squares;\n    }\n\n    private int getLength(int row, int col, int[][] matrix, int[][] memo) {\n        if (row >= matrix.length || col >= matrix[row].length || matrix[row][col] == 0) return 0;\n        if (memo[row][col] != 0) return memo[row][col];\n\n        memo[row][col] = Math.min(getLength(row + 1, col, matrix, memo),\n                Math.min(getLength(row, col + 1, matrix, memo), getLength(row + 1, col + 1, matrix, memo))) + 1;\n\n        return memo[row][col];\n    }\n}\n```\n```\npublic class CountSquareMatricesWithAllOnesBottomUp2DApproach {\n    public int countSquares(int[][] matrix) {\n        int[][] length = new int[matrix.length + 1][matrix[0].length + 1];\n        int squares = 0;\n\n        for (int row = matrix.length - 1; row >= 0; row--) {\n            for (int col = matrix[row].length - 1; col >= 0; col--) {\n                if (matrix[row][col] == 0) continue;\n\n                length[row][col] = Math.min(length[row + 1][col],\n                        Math.min(length[row][col + 1], length[row + 1][col + 1])) + 1;\n                squares += length[row][col];\n            }\n        }\n\n        return squares;\n    }\n}\n```\n```\npublic class CountSquareMatricesWithAllOnesBottomUp1DApproach {\n    public int countSquares(int[][] matrix) {\n        int[] length = new int[matrix[0].length + 1];\n        int squares = 0;\n\n        for (int row = matrix.length - 1; row >= 0; row--) {\n            int prev = 0;\n\n            for (int col = matrix[row].length - 1; col >= 0; col--) {\n                if (matrix[row][col] == 0) {\n                    prev = length[col];\n                    length[col] = 0;\n                    continue;\n                }\n\n                int current = length[col];\n                length[col] = Math.min(length[col], Math.min(length[col + 1], prev)) + 1;\n                prev = current;\n                squares += length[col];\n            }\n        }\n\n        return squares;\n    }\n}\n```
[]