[C++] 2 solutions of how I like to think about DP in general
The idea:\n\nWhenever I see a problem, my go to method is usually recursion. Since most DP solutions are essentially optimization of recursive solutions I find 
The idea:\n\nWhenever I see a problem, my go to method is usually recursion. Since most DP solutions are essentially optimization of recursive solutions I find it helpful to narrow down the way of comming up with a solution. With that being said, I do feel like for this problem in particular, it is probably easier thinking it in a bottom up perspective. \n\nNow, let us define a function `T(n,m)` where it\'s result is the size of the biggest square with its lower right corner at `matrix[n][m]`. Notice that this is also the max number of squares with their lower right corner at `matrix[n][m]`. Let us define a recurence relationship: `T(n,m) = min(T(n-1,m), T(n-1,m-1), T(n, m-1)) + 1` where `matrix[n][m] = 1`. Why is this true? Well, you just kind of have to stare that the squares and realize that a size `k` square is actually just a merger of three size `k-1` square around its lower right corner. \n\nHow does this help us with the problem. Suppose we run `T(n,m)` on all the entries of the input matrix, we would get something, like this:\n```\n0 1 1 1       0 1 1 1\n1 1 1 1  ->   1 1 2 2\n0 1 1 1       0 1 2 3\n```\nNotice that summing all the entries together gives us the answer `1+1+1+1+1+2+2+1+2+3=15` which is the correct answer. Since `T(n,m)` gives us the max number of squares with their lower right corner at `matrix[n][m]` and we ran it on all possible lower right corners, it got us the total number of sub-matrix-squares.  \n\nSolution 1: recursion with memorization\n\nThe number of unique subcases are `n*m` giving us the follow algorithm in c++\n```\nclass Solution {\n    vector<vector<int>> mem;\n    vector<vector<int>>* matrix;\n    int result = 0;\n    \n    int helper(int n, int m) {\n        if(mem[n][m] != -1) {\n            return mem[n][m];\n        }\n        \n        mem[n][m] = min(helper(n-1,m), min(helper(n-1,m-1), helper(n,m-1))) + 1;\n        if((*matrix)[n][m] == 0) {\n            mem[n][m] = 0;\n        }\n        result += mem[n][m];\n        return mem[n][m];\n        \n    }\n    \npublic:\n    int countSquares(vector<vector<int>>& matrix) {\n        this->matrix = &matrix;\n        int n = matrix.size();\n        int m = matrix[0].size();\n        mem = vector<vector<int>>(n,vector<int>(m,-1));\n        for(int i = 0; i < max(n,m); i++) {\n            if(i < n) {\n                mem[i][0] = matrix[i][0];\n                result += matrix[i][0];\n            }\n            if(i != 0 && i < m) {\n                mem[0][i] = matrix[0][i];\n                result += matrix[0][i];\n            }\n        }\n        \n        helper(n-1,m-1);\n        \n        return result;\n    }\n};\n```\nBefore you say anything, this is not a refined and elegant. I wrote this just as a proof of concept that a top down recursion works and it did past submission. The running time is ```O(n*m)``` while the Space Complexity is `O(n*m)` as well. However, since we have a tight upper bound on the number of unique cases, we can turn this approach into bottom up.\n\nSolution 2:\n```\nclass Solution {\n    \npublic:\n    int countSquares(vector<vector<int>>& matrix) {\n        int result = 0;\n        int n = matrix.size();\n        int m = matrix[0].size();\n        for(int i = 0; i < n; i++) {\n            for(int j = 0; j < m; j++) {\n                if(i == 0 || j == 0) {\n                    result += matrix[i][j];\n                } else if(matrix[i][j] == 1) {\n                    matrix[i][j] = min(matrix[i-1][j], min(matrix[i-1][j-1], matrix[i][j-1])) + 1;\n                    result += matrix[i][j];\n                }\n            }\n        }\n        \n        return result;\n    }\n};\n```\nMuch shorter and elegant. We uses the same recurrence relationship and concept just in reverse. Since we don\'t have to rely on recursion it runs faster and uses less space. This approach also makes it possible for us to actually use the input matrix as the DP array. The time complexity is ```O(n*m)``` and the space complexity is `O(1)`.\n\nP.S. I\'m on a mission to write a discussion post for all the problems I solve as excercises to practice for interviews. Please tell me if there is any problems you have with my explanations!
[]