编写题解 1642: 蓝桥杯算法训练VIP-暗恋 动态规划解决

解题思路: 

       dp[i][j]表示以a[i][j]为右下角形成的最大正方体边长，默认为1，从第二行第二列开始遍历，将a[i][j]，分别与a[i - 1][j] , a[i][j - 1],a[i-1][j-1]进行比较

若相等，说明这四个元素可以组成一个边长为2的正方形；

       然后从dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]中选出最小值min,   dp[i][j]=min+1;(正方形边长加1)

       遍历得到dp最大值再平方       （嘴太笨了）

注意事项:

参考代码:

#include<iostream>

#include<algorithm>

using namespace std;

#define Max 201

int a[Max][Max] = { 0 };

int dp[Max][Max] = { 0 };  //dp[i][j]表示以a[i][j]为右下角形成的最大正方体边长

int main() 

{

    int n, m;

    cin >> n >> m;

    for (int i = 1; i <= n; i++)

    {

        for (int j = 1; j <= m; j++)

        {

            cin >> a[i][j];

            dp[i][j] = 1;//默认为一

        }

    }

    int sum = 1;//默认正方形边长为1

    for (int i = 2; i <= n; i++)

    {

        for (int j = 2; j <= m; j++)

        {

            if (a[i][j] == a[i - 1][j]&& a[i][j] == a[i][j - 1]&&a[i][j]==a[i-1][j-1])

            {

            dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;//三个里面选出最小的

            sum = max(sum, dp[i][j]);

            }

        }

    }

    cout << sum*sum << endl;

    return 0;

}