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

• 题目考察的知识点 : 动态规划
• 题目解答方法的文字分析：

1. 定义一个二维整数数组 dp，其中 dp[i][j] 表示以第 i 行、第 j 列为右下角的最大正方形的边长。
2. 对于每个位置 (i, j)，如果 matrix[i][j] 为 'C'，那么它可能成为某个正方形的右下角，此时我们需要找到它上面、左边和左上角三个位置的最小值，并加上 1，作为以这个位置为右下角的最大正方形的边长。具体而言，我们有如下动态规划转移方程：dp[i][j]=min{dp[i−1][j],dp[i][j−1],dp[i−1][j−1]}+1, if matrix[i][j]=′C′
3. 每个正方形都必须是连续的一片区域，因此除了第一行和第一列以外的位置，如果 matrix[i][j] 为 'E'，则 dp[i][j] 必须设为 0。
4. 最终答案即为 dp 中所有元素的最大值的平方，因为正方形的面积等于边长的平方。

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param land char字符型二维数组 
# @return int整型
#
class Solution:
    def maximalSquare(self , land: List[List[str]]) -> int:
        m, n = len(land), len(land[0])
        dp = [[0] * n for _ in range(m)]
        ans = 0
        for i in range(m):
            for j in range(n):
                if land[i][j] == 'C':
                    if i == 0 or j == 0:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                    ans = max(ans, dp[i][j])
                else:
                    dp[i][j] = 0
        return ans * ans