Recursion | Recursion + Memoization | Iterative | Java Solution
Recursion [TLE]\n\njava\nclass Solution {\n    public int countSquares(int[][] matrix) {\n        int n = matrix.length;\n        int m = matrix[0].length;\n   
1. Recursion [TLE]\n\n```java\nclass Solution {\n    public int countSquares(int[][] matrix) {\n        int n = matrix.length;\n        int m = matrix[0].length;\n        int count = 0;\n        \n        int[][] moves = {{1, 0}, {0, 1}, {1, 1}};\n        \n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < m; j++) {\n                if (matrix[i][j] == 0) {\n                    continue;\n                }\n                \n                count += solve(matrix, n, m, i, j, moves);\n            }\n        }\n        \n        return count;\n    }\n    \n    private int solve(int[][] matrix, int n, int m, int i, int j, int[][] moves) {\n        if (i < 0 || j < 0 || i >= n || j >= m || matrix[i][j] == 0) {\n            return 0;\n        }\n        \n        int res = Integer.MAX_VALUE;\n        \n        for (int[] move : moves) {\n            int new_i = i + move[0];\n            int new_j = j + move[1];\n            \n            res = Math.min(res, solve(matrix, n, m, new_i, new_j, moves) + 1);\n        }\n        \n        return res;\n    }\n}\n```\n\n2. Recursion + Memoization [Accepted]\n\n```java\nclass Solution {\n    public int countSquares(int[][] matrix) {\n        int n = matrix.length;\n        int m = matrix[0].length;\n        int count = 0;\n        \n        int[][] moves = {{1, 0}, {0, 1}, {1, 1}};\n        \n        int[][] dp = new int[n + 1][m + 1];\n        for (int[] a : dp) {\n            Arrays.fill(a, -1);\n        }\n        \n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < m; j++) {\n                if (matrix[i][j] == 0) {\n                    continue;\n                }\n                \n                count += solve(matrix, n, m, i, j, moves, dp);\n            }\n        }\n        \n        return count;\n    }\n    \n    private int solve(int[][] matrix, int n, int m, int i, int j, int[][] moves, int[][] dp) {\n        if (i < 0 || j < 0 || i >= n || j >= m || matrix[i][j] == 0) {\n            return 0;\n        }\n        \n        if (dp[i][j] != -1) {\n            return dp[i][j];\n        }\n        \n        int res = Integer.MAX_VALUE;\n        \n        for (int[] move : moves) {\n            int new_i = i + move[0];\n            int new_j = j + move[1];\n            \n            res = Math.min(res, solve(matrix, n, m, new_i, new_j, moves, dp) + 1);\n            dp[i][j] = res;\n        }\n        \n        return res;\n    }\n}\n```\n\n3. Iterative [Accepted]\n\n```java\nclass Solution {\n    public int countSquares(int[][] matrix) {\n        int n = matrix.length;\n        int m = matrix[0].length;\n        int count = 0;\n        \n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < m; j++) {\n                if (matrix[i][j] > 0 && i > 0 && j > 0) {\n                    matrix[i][j] = Math.min(matrix[i - 1][j - 1], Math.min(matrix[i - 1][j], matrix[i][j - 1])) + 1;\n                }\n                count += matrix[i][j];\n            }\n        }\n        \n        return count;\n    }\n}\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'Java']