221.Maximal Square

The recursion equation used in the solution is slightly different from the officical article, but the idea is the same.

Official article:

dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1
where dp[i][j] is the size of sqare with (i, j) as bottom-right corner.
This post:

dp[i][j] = min(dp[i+1][j], dp[i+1][j+1], dp[i][j+1]) + 1
where dp[i][j] is the size of sqare with (i, j) as upper-left corner.
For the DP solution, the hardest part is to find the recursion equation :)
Code:

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        return tabulation(matrix);
    }
    
    // 1. Brute force
    int bruteForce(vector<vector<char>>& matrix) {
        int res = 0;
        
        for(int i = 0; i < matrix.size(); ++i) {
            for(int j = 0; j < matrix[0].size(); ++j) {
                if (matrix[i][j] == '0') continue;
                
                int area = 1;
                int right = j + 1, low = i + 1;
                while(right < matrix[0].size() && low < matrix.size()) {
                    bool valid = true;
                    for(int row = i; row <= low; ++row) {
                        if (matrix[row][right] == '0') {
                            valid = false;
                            break;
                        }
                    }
                    
                    for(int col = j; col <= right; ++col) {
                        if (matrix[low][col] == '0') {
                            valid = false;
                            break;
                        }
                    }
                    
                    if (valid) {
                        area = max(area, (low - i + 1) * (right - j + 1));
                    } else {
                        area = max(area, (low - i) * (right - j));
                        break;
                    }
                    
                    ++right;
                    ++low;
                }
                res = max(res, area);
            }
        }
        
        return res;
    }
    
    // 2. Recursive.
    // TLE.
    int recursive(vector<vector<char>>& matrix) {
        if (matrix.empty()) return 0;
        
        int res = 0;
        for(int i = 0; i < matrix.size(); ++i) {
            for(int j = 0; j < matrix[0].size(); ++j) {
                res = max(res, helper(matrix, i, j));
            }
        }
        return res * res;
    }
    
    // Return the area of maximum square with (i, j) as upper-left corner.
    int helper(vector<vector<char>>& matrix, int i, int j) {
        if (i >= matrix.size() || j >= matrix[0].size()) return 0;
        if (matrix[i][j] == '0') return 0;
        return min(min(helper(matrix, i, j+1), helper(matrix, i+1, j)), 
                   helper(matrix, i+1, j+1)) + 1;
    }
    
    
    // 3. Memoization
    int memoization(vector<vector<char>>& matrix) {
        if (matrix.empty()) return 0;
        vector<vector<int>> mem(matrix.size(), vector<int>(matrix[0].size(), -1));
        
        int res = 0;
        for(int i = 0; i < matrix.size(); ++i) {
            for(int j = 0; j < matrix[0].size(); ++j) {
                res = max(res, solve(matrix, mem, i, j));
            }
        }
        return res * res;
    }
    
    int solve(vector<vector<char>>& matrix, vector<vector<int>>& mem, int i, int j) {
        if (i >= matrix.size() || j >= matrix[0].size()) return 0;
        if (mem[i][j] >= 0) return mem[i][j];
        if (matrix[i][j] == '0') return mem[i][j] = 0;
        mem[i][j] = min(min(solve(matrix, mem, i+1, j), solve(matrix, mem, i, j+1)),
                        solve(matrix, mem, i+1, j+1)) + 1;
        return mem[i][j];
    }
    
    
    // 4. Tabulation
    int tabulation(vector<vector<char>>& matrix) {
        if (matrix.empty()) return 0;
        
        int res = 0;
        vector<vector<int>> tab(matrix.size(), vector<int>(matrix[0].size()));

        for(int row = tab.size() - 1; row >= 0; --row) {
            for(int col = tab[0].size() - 1; col >= 0; --col) {
                if (col == matrix[0].size() - 1) {
                    tab[row][col] = matrix[row][col] == '0' ? 0 : 1;
                } else if (row == matrix.size() - 1) {
                    tab[row][col] = matrix[row][col] == '0' ? 0 : 1;
                } else if (matrix[row][col] == '0') {
                    tab[row][col] = 0;
                } else {
                    tab[row][col] = min(min(tab[row+1][col], tab[row][col+1]),
                                        tab[row+1][col+1]) + 1;
                }
                res = max(res, tab[row][col]);
            }
        }
        
        return res * res;
    }
};