题解 | #奶牛的活动面积#

知识点

二维动态规划

思路

我们考虑如何用O（nn）的时间复杂度，首先，对于land[i][j]，以它为右下角形成正方形，需要满足3个条件：

land[i-1][j-1]也能以右下角形成正方形X，

land[i][j]左侧的‘C’的数量（包括自己）需大于等于X的边长

land[i][j]上侧的‘C’的数量（包括自己）需大于等于X的边长

于是，我们可以采用一个DP[N][N][3]来记录当前节点的搜索情况，其中dp[i][j][k]中，i代表行，j代表列，k取值为0,1，2分别代表左侧连续C数，上侧连续C数以及作为当前节点作为正方形右下角情况下的正方形边长。

状态转移

首先初始化dp为0.这题维护的属性为最大，故对每个dp[i][k][2]取MAX，最终返回值为

当当前节点为'C'时，有以下状态转移方程：

dp[i][j][0]=dp[i][j-1][0]+1;//从上一列的左侧转移
dp[i][j][1]=dp[i-1][j][1]+1;//从上一行的上侧转移
if(dp[i][j][1]>=dp[i-1][j-1][2]+1&&dp[i][j][0]>=dp[i-1][j-1][2]+1)//判断条件
{
   dp[i][j][2]=dp[i-1][j-1][2]+1;//从上一行上一列那一个的边长转移
}
else dp[i][j][2]=1;//自己也可以构成正方形

当当前节点为‘E’时，没什么转移的了，3个属性都是0

代码 c++

#include <cstring>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param land char字符型vector<vector<>> 
     * @return int整型
     */
     int dp[1005][1005][3];
     //0zuo 1shang 2 zfxbianchang
    int maximalSquare(vector<vector<char> >& land) {
        memset(dp, 0, sizeof dp);
        int ans=-1;
        for(int i=1;i<=land.size();i++)
        {
            for(int j=1;j<=land.size();j++)
            {
                if(land[i-1][j-1]=='C')
                {
                    dp[i][j][0]=dp[i][j-1][0]+1;
                    dp[i][j][1]=dp[i-1][j][1]+1;
                    if(dp[i][j][1]>=dp[i-1][j-1][2]+1&&dp[i][j][0]>=dp[i-1][j-1][2]+1)
                    {
                        dp[i][j][2]=dp[i-1][j-1][2]+1;
                    }
                    else dp[i][j][2]=1;

                }
                else{
                      dp[i][j][0]=0;
                      dp[i][j][1]=0;
                      dp[i][j][2]=0;
        
                
                  }
                ans=max(ans,dp[i][j][2]);
            }
        }
       
       return ans*ans;

    }
};