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

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。

题目考察的知识点

动态规划

题目解答方法的文字分析

这是一个经典的动态规划问题，我们可以使用动态规划的方法来解决。

首先，我们定义一个二维数组dp，其中dp[i][j]表示以(i, j)为右下角的最大正方形的边长。我们要找到最大的dp[i][j]，并根据边长计算正方形的面积。

接下来，我们考虑状态转移方程。对于dp[i][j]，如果land[i][j]是'E'，那么dp[i][j]为0，因为以(i, j)为右下角的正方形无法包含奶牛；如果land[i][j]是'C'，那么dp[i][j]的值取决于dp[i-1][j]、dp[i][j-1]和dp[i-1][j-1]的最小值，再加上1，表示以(i, j)为右下角的正方形的边长。因此，状态转移方程为：dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;

最后，我们可以在动态规划的过程中更新最大面积，即最大边长的平方。

本题解析所用的编程语言

C++

完整且正确的编程代码

class Solution {
public:
    int maximalSquare(vector<vector<char>>& land) {
        int m = land.size(); // 获取地块的行数
        int n = land[0].size(); // 获取地块的列数

        vector<vector<int>> dp(m, vector<int>(n, 0)); // 创建动态规划数组dp，初始化为0
        int maxSide = 0; // 记录最大边长

        // 初始化dp数组的第一行和第一列
        for (int i = 0; i < m; i++) {
            dp[i][0] = land[i][0] == 'C' ? 1 : 0;
            maxSide = max(maxSide, dp[i][0]);
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = land[0][j] == 'C' ? 1 : 0;
            maxSide = max(maxSide, dp[0][j]);
        }

        // 填充dp数组，使用状态转移方程
        // dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (land[i][j] == 'C') {
                    dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    maxSide = max(maxSide, dp[i][j]);
                }
            }
        }

        return maxSide * maxSide; // 返回最大面积，即最大边长的平方
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！