C++ DP Solution, Explaination, without modifying the input matrix
What we need to know here is how to make a square\nFor example, if we scan the matrix from the left top to right bottom(input matrix denoted by m), m[i][j] will
What we need to know here is **how to make a square**\nFor example, if we scan the matrix from the left top to right bottom(input matrix denoted by m), ```m[i][j]``` will be the **right bottom** of a side n square:\n- side 1 square: if ```m[i][j]==1```\n- side 2 square: if ```m[i][j]==1``` and``` (m[i-1][j]==1 and m[i-1][j-1]==1 and m[i][j-1]==1) ```\n             -> (```m[i-1][j], m[i-1][j-1],  m[i][j-1]``` are **side 1 squares**)\n- side 3 square: if ```m[i][j]==1``` and (```m[i-1][j], m[i-1][j-1],  m[i][j-1]``` are **side 2 squares**)\n...\n->\n- side n square: if ```m[i][j]==1``` and (```m[i-1][j], m[i-1][j-1],  m[i][j-1]``` are side n-1 squares)\n\nthus we need a matrix to record the largest square ```(m[i-1][j], m[i-1][j-1],  m[i][j-1])``` can make, and by comparing we can know the maximum size of square ```m[i][j]``` can make. \nSo we can use a dp matrix to do that, ```dp[i][j]``` means the maximum size of square we can get with ```m[i][j]``` to be the right buttom of that square.\nBy summing up the numbers in the dp matrix, we can get our result.\n\n```C++\nclass Solution {\npublic:\n    int countSquares(vector<vector<int>>& matrix) {\n        int m = matrix.size(), n = matrix[0].size();\n        vector<vector<int>> dp(m, vector<int>(n, 0));\n        int res = 0;\n        for (int i=0; i<m; i++) {\n            for (int j=0; j<n; j++) {\n                if (matrix[i][j]==1) {\n                    if (i-1>=0 && j-1>=0)\n                        dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1])+1;\n                    else \n                        dp[i][j] = 1;\n                    \n                    res += dp[i][j];\n                }\n            }\n        }\n        return res;\n    }\n};\n```
['Dynamic Programming', 'C', 'C++']