Leetcode 221 Maximal Square

1. 问题描述

　　给出一个二维的01矩阵，计算出包含1做多的方阵，并返回包含1的个数。
　　

2. 方法与思路

　　利用动态规划的思想。以右下角基准，找出最大边长。状态转移方程如下：
　　dp[i][j] = min(d][i-1][j], dp[i][j-1], dp[i-1][j-1]) +1;
　　其中dp[i][j]表示以(i,j)为右下角的全1矩阵的最大边长。
　　

class Solution {
public:
    int minNum(int a, int b, int c)
    {
        int tmp = a < b?a:b;
        return tmp < c?tmp:c;
    }
    int maximalSquare(vector<vector<char>>& matrix) {

        int m,n,i,j,re=0;

        if(matrix.size() == 0) 
            return 0;

        m = matrix.size();
        n = matrix[0].size();

        int dp[m][n];
        for(i = 0; i < m; i++)
            for(j = 0; j < n; j++)
                dp[i][j] = 0;
        for(i = 0; i < m; i++)
        {
            for(j = 0; j < n; j++)
            {
                dp[i][j] = matrix[i][j] - ‘0‘;
                if(i && j && dp[i][j])
                {
                    dp[i][j] = minNum(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) + 1; 
                }
                re = max(re,dp[i][j]);
            }
        }

        return re*re;
    }
};