Leetcode 1277: Count Square Submatrices with All Ones

https://leetcode.com/problems/count-square-submatrices-with-all-ones/description/

Notes:

This question can be solved by dynamic programming.

This question essentially is the same as the one asking for the largest square of all 1s. (Leetcode 221 Maximal Square)

Let use dp[i][j] represent the edge length of the largest square ending with matrix[i][j] which is the bottom-right corner element.

Then dp[i][j] = 1 + min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]).

This question is asking for the number of the squares, so the new found squares should always ending with matrix[i][j] which is the bottom-right corner element.

Thus, we just need to update the counting by adding dp[i][j].

See the code below:

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        int res = 0, m = matrix.size(), n = matrix.front().size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for(int i=1; i<=m; ++i) {
            for(int j=1; j<=n; ++j) {
                if(matrix[i-1][j-1] == 0) continue;
                dp[i][j] = 1 + min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]));
                res += dp[i][j];
            }
        }
        return res;
    }
};