Recursive DP ->iterative DP reusing matrix||100%
Intuition\n Describe your first thoughts on how to solve this problem. \n1st approach is using top-down design, recursion with memo\n\nLater try other approach.
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n1st approach is using top-down design, recursion with memo\n\nLater try other approach.\n2nd approach is an iterative DP reusing matrix with extra space O(1)\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Declare 2D array `dp`\n2. The recursive function `int f(int i, int j, vector<vector<int>>& matrix)` computes how many squares are to the bottom-right (i, j)-term(inclusive)\n3. In `countSquares(vector<vector<int>>& matrix)` initialize all elements in `dp` with -1; set `cnt=0`\n4. Use a double-loop to proceed `cnt+=f(i, j, matrix)`\n5. `cnt` is the answer\n6. Rewrite recursive one into iterative one & reuse` matrix` as state matrix,only extra O(1) space.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(r\\cdot c)$$ \n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(r\\cdot c)$$ \niterative: $O(1)$\n# Code ||recursion with memo\n```cpp []\nclass Solution {\npublic:\n    int dp[300][300];\n    int f(int i, int j, vector<vector<int>>& matrix){\n        if (i<0||j<0|| matrix[i][j]==0 ) return 0;\n        if (dp[i][j]!=-1) return dp[i][j];\n        return dp[i][j]=1+min({f(i-1, j, matrix),f(i-1, j-1, matrix),f(i, j-1, matrix)});\n    }\n    int countSquares(vector<vector<int>>& matrix) {\n        const int r=matrix.size(), c=matrix[0].size();\n        memset(dp, -1, sizeof(dp));\n        int cnt=0;\n        for(int i=0; i<r; i++)\n            for(int j=0; j<c; j++)\n                cnt+=f(i, j, matrix);\n        return cnt;\n    }\n};\n\n\n\nauto init = []() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n\n```\n# C++ iterative DP reusing matrix||0ms beats 100%\n```\nclass Solution {\npublic:\n    int countSquares(vector<vector<int>>& matrix) {\n        const int r=matrix.size(), c=matrix[0].size();\n        int cnt=0;\n        cnt=count(matrix[0].begin(), matrix[0].end(), 1);\n        for(int i=1; i<r; i++) \n            cnt+=matrix[i][0];;\n        \n        for(int i=1; i<r; i++)\n            for(int j=1; j<c; j++){\n                if (matrix[i][j]==0) continue;\n                matrix[i][j]=1+min({matrix[i-1][j], matrix[i-1][j-1], matrix[i][j-1]});\n                cnt+=matrix[i][j];\n            }\n        return cnt;\n    }\n};\n\n\nauto init = []() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```
['Array', 'Dynamic Programming', 'Recursion', 'Memoization', 'Matrix', 'C++']