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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param land char字符型二维数组 
     * @return int整型
     */
    public int maximalSquare (char[][] land) {
        int maxSide = 0;
        if (land.length == 0 || land[0].length == 0) {
            return maxSide;
        }
        int rows = land.length, cols = land[0].length;
        int[][] dp = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (land[i][j] == 'C') {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    }
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
            }
        }
        return maxSide * maxSide;
    }
}

本题知识点分析：

1.动态规划

2.数组遍历

3.API函数

本题解题思路分析：

1.dp数组用于存储最大正方形的边长

2.dp数组初始化 if (i == 0 || j == 0) dp[i][j] = 1;

3.dp公式推导 dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1; 左上，上，左，三种的最小值+1，就是右下

4.每次更新dp值后，将当前dp[i][j]的值与maxSide进行比较，取较大值作为新的maxSide，边长

本题使用编程语言: Java