lintcode---最大正方形

题目描述：
在一个二维01矩阵中找到全为1的最大正方形

样例：
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
返回 4

思路讲解：
首先我们分析下，由于标签中提到动态规划，我们就考虑其的状态转移方程，由于我们判断一个是不是正方形，就需要判断p[i][j]、p[i-1][j]、p[i][j-1]、p[i-1][j-1]这四个点如果都是以，就构成了一个2*2的正方形，但是如何实行状态转移呢？我们利用p[i][j]表示其位置为右下角的最大正方形，这样我们就可以运用动态规划了，p[i][j]依靠p[i-1][j]、p[i][j-1]、p[i-1][j-1]三个的状态，并且其依赖于三个中最小的数。这样我们只需要遍历p数组，得到最大值就好了。

代码详解：

class Solution {
public:
    /*
     * @param matrix: a matrix of 0 and 1
     * @return: an integer
     */
    int maxSquare(vector<vector<int>>& matrix) {
        // write your code here
        int m=matrix.size();
        int n=matrix[0].size();
        int **dp=new int*[m];
        for(int i=0;i<m;i++){
            dp[i]=new int [n];
        }

        int res=INT_MIN;
        for(int i=0;i<m;i++){
            dp[i][0]=matrix[i][0];
            res=max(dp[i][0],res);
        }

        for(int i=0;i<n;i++){
            dp[0][i]=matrix[0][i];
            res=max(dp[0][i],res);
        }

        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if(matrix[i][j]){
                    dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1;
                }else{
                    dp[i][j]=0;
                }
                if(dp[i][j]>res){
                    res=dp[i][j];
                }
            }
        }
        return res*res;
    }
    int min(int a,int b,int c)
    {
        int tmp=a>b?b:a;
        return tmp>c?c:tmp;
    }
};