力扣动态规划最大正方形

Question

请问我哪一步有问题啊，为什么这种情况算的是错的啊？

int dp[301][301];  //dp[i][j]表示以matrix[i][j]为右下角的只包含1的最大正方形边长
int min(int x,int y,int z)
{
    int demp;
    demp=x>y? y:x;
    if(demp>z) demp=z;
    return demp;
}
int maximalSquare(char** matrix, int matrixSize, int* matrixColSize) {
    int i,j,max=0;
    for(i=0;i<matrixSize;i++)
    {
        for(j=0;j<matrixColSize[0];j++)
        {
            if(i==0||j==0)
                dp[i][j]=matrix[i][0]-'0';
            else
            {
                if(matrix[i][j]=='1')
                    dp[i][j]=1+min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]);
                else
                    dp[i][j]=0; 
            }
            if(dp[i][j]>max)
                max=dp[i][j];
        }
    }
    return pow(max,2);
}

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

问题描述： 在一个由0和1组成的矩阵中，找到只包含1的最大正方形，并返回其面积。 问题分析： 题目要求找到最大的正方形，我们自然而然会想到使用动态规划来解决这个问题。我们定义一个二维数组dp，其中dp[i][j]表示以matrix[i][j]为右下角的只包含1的最大正方形的边长。由于正方形是边长相等的矩形，因此我们只需要存储边长即可。 对于matrix[i][j]，如果它是1，那么可以由dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]这三个位置的值转移而来，即： dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 其中min表示取三个数的最小值，因为只有三个方向的值相同并且都大于等于1时，才能组成正方形。如果matrix[i][j]为0，则dp[i][j]的值为0，因为以0为右下角的正方形不存在。 最后，我们遍历dp数组，找到最大的边长max，返回max的平方作为最大正方形的面积。 问题解答： 问题一：哪一步有问题？为什么这种情况算的是错的？ 代码中最后返回的是最大边长的平方，而不是最大正方形的面积。应该将返回语句修改为return max * max; 例如，当输入矩阵为[[1,1,1],[1,1,0],[1,0,1]]时，预期输出为4，但代码输出为9。 问题二：如何规范回答格式？ 回答应该具有如下格式：

• 问题描述
• 问题分析（包括解决方法和思路等）
• 问题解答
• 可能的问题和解决方案 示例： 问题描述： 给定一个01矩阵，找到其中由1组成的最大正方形，并返回其面积。 问题分析： 题目要求找到最大的正方形，我们自然而然会想到使用动态规划来解决这个问题。我们定义一个二维数组dp，其中dp[i][j]表示以matrix[i][j]为右下角的只包含1的最大正方形的边长。由于正方形是边长相等的矩形，因此我们只需要存储边长即可。 对于matrix[i][j]，如果它是1，那么可以由dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]这三个位置的值转移而来，即： dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 其中min表示取三个数的最小值，因为只有三个方向的值相同并且都大于等于1时，才能组成正方形。如果matrix[i][j]为0，则dp[i][j]的值为0，因为以0为右下角的正方形不存在。 最后，我们遍历dp数组，找到最大的边长max，返回max的平方作为最大正方形的面积。 问题解答： int maximalSquare(char** matrix, int matrixSize, int* matrixColSize) { int dp[301][301]; //dp[i][j]表示以matrix[i][j]为右下角的只包含1的最大正方形边长 int i, j, max = 0; for (i = 0; i < matrixSize; i++) { for (j = 0; j < matrixColSize[0]; j++) { if (i == 0 || j == 0) { dp[i][j] = matrix[i][0] - '0'; } else { if (matrix[i][j] == '1') { dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]); } else { dp[i][j] = 0; } } if (dp[i][j] > max) { max = dp[i][j]; } } } return max * max; } 问题三：可能的问题和解决方案
• 数组越界问题 在遍历dp数组的时候，注意要判断i和j都不为0的情况，否则会访问dp数组的[-1]位置，导致数组越界。
• 实现最小值函数 由于C语言中没有自带的min函数，需要自己实现取三个数的最小值的函数。 int min(int x, int y, int z) { int temp = x > y ? y : x; if (temp > z) { temp = z; } return temp; }