Leetcode 1277. Count Square Submatrices with All Ones (python + cpp)

题目

解法：动态规划

其实这道题目跟221 maximum square. 那道题里面dp数组每个位置代表以这个位置作为右下角点的最大square的边长多大。而这边只需要把那个dp数组全部加起来就是答案了。因为dp每个位置的值代表以这个位置作为右下角的点的square有多少个

python版本

class Solution:def countSquares(self, matrix: List[List[int]]) -> int:m = len(matrix)n = len(matrix[0])dp = [[0]*n for _ in range(m)]for i in range(m):if matrix[i][0] == 1:dp[i][0] = 1for i in range(n):if matrix[0][i] == 1:dp[0][i] = 1for i in range(1,m):for j in range(1,n):if matrix[i][j] == 1:dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) + 1else:dp[i][j] = 0ans = 0for i in range(m):for j in range(n):ans += dp[i][j]return ans;

C++版本

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