Java DP with explanation
Idea came from this amazing article - https://www.techiedelight.com/find-size-largest-square-sub-matrix-1s-present-given-binary-matrix/\ndp[i][j] denotes the ma
Idea came from this amazing article - https://www.techiedelight.com/find-size-largest-square-sub-matrix-1s-present-given-binary-matrix/\ndp[i][j] denotes the maximum size of 1s-square that ends at matrix[i][j]. The image (it is also from the above post) below helped me to understand how it works.\n\n![image](https://assets.leetcode.com/users/mavs0603/image_1575394277.png)\n\n```\nclass Solution {\n    public int countSquares(int[][] matrix) {\n        int R = matrix.length;\n        int C = matrix[0].length;\n        int[][] dp = new int[R][C];\n        int res = 0;\n        for(int i = 0; i < R; i++){\n            for(int j = 0; j < C; j++){\n                dp[i][j] = matrix[i][j];\n                if(i > 0 && j > 0 && matrix[i][j] == 1){\n                    dp[i][j] = Math.min(dp[i - 1][j - 1], \n                                        Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;\n                }\n                res += dp[i][j];\n            }\n        }\n        return res;\n    }\n}\n```
[]