最大正方形-【动态规划】

题目描述： 在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。 输入: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0

输出: 4 思路： 先确定dp数组的含义，用dp[i][j]数组来表示包括i行以及i行前的，包括j列以及j列前的，满足条件的最大正方形。并且只对matrix数组值为'1'的点，求dp[][]的值，其余的赋值0即可

动态规划思考量最大的还是动态转移方程

1.本题的关键点就是想通，状态转移方程，dp[ i ][ j ] = min(dp[ i-1 ][ j-1 ] , dp[ i-1 ][ j ] , dp[ i ][ j-1 ]) + 1, 可以结合上图想一下 边长2推出边长3的过程。 2.由于第一行第一列的元素是没有三个相邻元素来索引，所以需要构造半层padding dp = [ [ 0 for _ in range(n+1)] for _ in range(m+1) ]

参考代码：

#include <bits/stdc++.h>
using namespace std;
int a[101][101],b[101][101],m,n;
inline int Min(int a,int b,int c) {return min(a,min(b,c));} 
int main()
{
    while(cin>>n>>m)
    {
        int ans = 0;
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j)
                scanf("%d",&a[i][j]);
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j)
                b[i][j] = a[i][j]?Min(b[i][j-1],b[i-1][j],b[i-1][j-1])+1:0, //b[i][j]是前面有多少个连续的1 
                ans = max(ans,b[i][j]);
        cout<<ans<<endl;
    }
    return 0;
}