let's visualize with clear understanding, with added YouTube video
YouTube solution https://youtu.be/I7O4cSV1JYo\n# Intuition and Approach\nlet me tell you few things :- \n\n1) at every cell of matrix if the value is 1 then tha
# YouTube solution https://youtu.be/I7O4cSV1JYo\n# Intuition and Approach\nlet me tell you few things :- \n\n1) at every cell of matrix if the value is **1** then that cell is **eligible that there could be 1 or more squares** end at that cell.\n\n**if(matrix[i][j]==1)** ===> **(i, j)** cordinates can have one or more ending sqaures.\n\n2) the sum of all such squares ending at every cell would give us total number of sqares in the matrix.\n**ans = sum of all eligible cordinates squares**\n\nwith above intution we can proceed further, we can go in tabulation method in **Bottom-Up approach** \n\ncreate a **DP[][] = new int[m+1][n+1]** (m and n are rows and columns in matrix)\n\n**why n+1 , m+1?** ==> because to start condition, we need to mimic the logic as below :- \n\nfor i 0 to m\nfor j = 0 to n \n**if(matrix[i][j]==1)**\n**dp[i+1][j+1] = 1+Math.min(dp[i][j], Math.min(dp[i+1][j], dp[i][j+1]))**\ni know , some of your would have a question that why and what is this??\n\nso let me explain it, **dp[i][j] , dp[i+1][j]  and dp[i][j+1]**  all these three cell in the DP is actually holding the result **how many Square were ending** at those corresponding cordinates.\ni am adding 1 to it because any waay we have found the 1 in matrix.\n\nnow can observe that ==> \n\n                       dp[i][j+1] ==> right side cordinate result\n                       dp[i+1][j] ==> below cordinate result\n                       dp[i][j] ===> cordinate result\n=====> to find the dp[i+1][j+1] ==> we need the **min of above three value result** \n===> because min value would make sure that we can add it 1 more **legit** value to the cordinate (i+1, j+1) this will give the largest possible value for this cordinate, hence it would be like below :- \n\n**dp[i+1][j+1] = 1+Math.min(dp[i][j], Math.min(dp[i+1][j], dp[i][j+1]))**\n\nand we would keep on adding the value to variable say **ans**\n\nans += dp[i+1][j+1] (**we are adding all the ending sqauares result**)\n\nreturn **ans** finally.\n\n\n# Code\n```java []\nclass Solution {\n    public int countSquares(int[][] matrix) {\n    int dp[][] = new int[matrix.length+1][matrix[0].length+1];\n    int ans = 0; \n    for(int i=0; i<matrix.length; i++)\n    {\n      for(int j=0; j<matrix[0].length; j++)\n      {\n        if(matrix[i][j]==1)\n        dp[i+1][j+1] = 1 + Math.min(dp[i][j], Math.min(dp[i+1][j], dp[i][j+1]));\n        ans += dp[i+1][j+1];\n      }  \n    }  \n    return ans;  \n    }\n}\n```\n```C# []\nclass Solution {\n    public int CountSquares(int[][] matrix) {\n    int [,]dp = new int[matrix.Length+1, matrix[0].Length+1];\n    int ans = 0; \n    for(int i=0; i<matrix.Length; i++)\n    {\n      for(int j=0; j<matrix[0].Length; j++)\n      {\n        if(matrix[i][j]==1)\n        dp[i+1,j+1] = 1 + Math.Min(dp[i,j], Math.Min(dp[i+1,j], dp[i,j+1]));\n        ans += dp[i+1,j+1];\n      }  \n    }  \n    return ans;  \n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    int countSquares(std::vector<std::vector<int>>& matrix) {\n        int rows = matrix.size();\n        int cols = matrix[0].size();\n        std::vector<std::vector<int>> dp(rows + 1, std::vector<int>(cols + 1, 0));\n        \n        int ans = 0;\n        for (int i = 0; i < rows; ++i) {\n            for (int j = 0; j < cols; ++j) {\n                if (matrix[i][j] == 1) {\n                    dp[i + 1][j + 1] = 1 + std::min({dp[i][j], dp[i + 1][j], dp[i][j + 1]});\n                    ans += dp[i + 1][j + 1];\n                }\n            }\n        }\n        \n        return ans;\n    }\n};\n\n```\n```Python []\nclass Solution:\n    def countSquares(self, matrix):\n        rows, cols = len(matrix), len(matrix[0])\n        \n        # Initialize dp array with an extra row and column\n        dp = [[0] * (cols + 1) for _ in range(rows + 1)]\n        \n        ans = 0\n        for i in range(rows):\n            for j in range(cols):\n                if matrix[i][j] == 1:\n                    dp[i + 1][j + 1] = 1 + min(dp[i][j], dp[i + 1][j], dp[i][j + 1])\n                    ans += dp[i + 1][j + 1]\n        \n        return ans\n\n```\n
['Array', 'Math', 'Dynamic Programming', 'Recursion', 'Python', 'C++', 'Java', 'C#']