LeetCode 221. 最大正方形（动态规划详解 + C语言实现）

题目描述给定一个由0和1组成的二维矩阵找到只包含1的最大正方形并返回其面积。示例输入 [ [1,0,1,0,0], [1,0,1,1,1], [1,1,1,1,1], [1,0,0,1,0] ] 输出4 解题思路动态规划这道题是一个非常经典的二维 DP 问题关键在于如何定义状态。 状态定义定义dp[i][j] 表示 以 (i, j) 为右下角 的最大正方形的边长⚠️ 注意必须是“右下角”这是本题的核心 状态转移方程如果当前位置是1dp[i][j] min( dp[i-1][j], // 上 dp[i][j-1], // 左 dp[i-1][j-1] // 左上 ) 1 为什么取最小值因为要形成一个正方形三边必须都满足上面够长左边够长左上角也要能扩展 本质是短板决定最大正方形 边界情况第一行和第一列dp[i][j] 1如果 matrix[i][j] 1 最终结果维护一个最大边长maxLen面积 maxLen * maxLen C语言实现#include stdlib.h int min(int a, int b, int c) { int t a b ? a : b; return t c ? t : c; } int maximalSquare(char** matrix, int matrixSize, int* matrixColSize) { if (matrixSize 0) return 0; int m matrixSize; int n matrixColSize[0]; int** dp (int**)malloc(sizeof(int*) * m); for (int i 0; i m; i) { dp[i] (int*)calloc(n, sizeof(int)); } int maxLen 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (matrix[i][j] 1) { if (i 0 || 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; } if (dp[i][j] maxLen) { maxLen dp[i][j]; } } } } // 释放内存 for (int i 0; i m; i) { free(dp[i]); } free(dp); return maxLen * maxLen; }⏱️ 复杂度分析时间复杂度O(m * n)空间复杂度O(m * n) 空间优化进阶可以优化为一维 DP滚动数组dp[j] min(dp[j], dp[j-1], prev) 1其中dp[j]→ 上dp[j-1]→ 左prev→ 左上 空间优化到O(n) 总结这题的关键只有一句话✅dp[i][j] 表示以当前点为右下角的正方形边长再记住✅正方形扩展取决于最短边min