今天带来P1387 最大正方形，一道动态规划经典题。先贴一下代码。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> vec(n,vector<int>(m));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>vec[i][j];
        }
    }
    vector<vector<int>> dp(n, vector<int>(m, 0));
    int max_side = 0;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (vec[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] > max_side) {
                    max_side = dp[i][j];
                }
            }
        }
    }

    cout << max_side << endl;
    return 0;
}

这题要求一个最大的正方形，直接枚举肯定是复杂度很高的，那么有没有什么别的方法。先来介绍一下动态规划，动态规划是一种通过将复杂问题分解为相互重叠的子问题来高效求解的算法思想，其核心在于记忆化存储子问题的解以避免重复计算。具体来说，动态规划通常采用自底向上或带备忘录的自顶向下方法，通过状态转移方程描述问题的最优子结构（即当前状态如何由之前状态推导），从而逐步构建出整体问题的最优解。它适用于具有重叠子问题和最优子结构性质的问题，如背包问题、最短路径等，能够将指数级暴力解法优化为多项式时间复杂度。那么在这道题中，就是正方形的大小，比如一个边长为3的正方形之中肯定有一个边长为2的正方形，边长为2的正方形之中肯定有一个边长为1的正方形。所以，我们就可以先从为1的点开始，为0的点都记为0，为1的点，如果是在第一排或者第一列就记为1，其余的按照这个点，左上，左边，上面三个点中最小的加1，就是这个点的边数。这是为什么呢，假设，周围有0，那肯定不会有更大的正方形，那么就是0+1=1，也就是自己本身。如果周围都是1，那就是2，依次类推，就把问题分解开来了。