dp

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 248;
int n;
int a[MAXN + 5];
// a[i]~a[j] 能变成 f[i][j]
// 如果 f[i][j] 为 0，则表示无法变成某个数
int f[MAXN + 5][MAXN + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int ans = 0;
    for (int len = 1; len <= n; len++)
    {
        for (int l = 1; l + len - 1 <= n; l++)
        {
            int r = l + len - 1;
            if (len == 1)
            {
                f[l][r] = a[l];
            }
            else
            {
                f[l][r] = 0;
                for (int mid = l; mid <= r - 1; mid++)
                {
                    if (f[l][mid] == f[mid + 1][r] &&
                        f[l][mid] != 0)
                    {
                        f[l][r] = f[l][mid] + 1;
                    }
                }
            }
            ans = max(ans, f[l][r]);
        }
    }
    cout << ans;
    return 0;
}

记忆化搜索求 dp

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 248;
int n;
int a[MAXN + 5];
int ans;
int book[MAXN + 5][MAXN + 5];
int dfs(int l, int r)
{
    if (book[l][r] != -1)
        return book[l][r];
    int res = 0;
    if (l == r)
        res = a[l];
    else
    {
        for (int i = l; i <= r - 1; i++)
        {
            int lres = dfs(l, i);
            int rres = dfs(i + 1, r);
            if (lres == rres && lres != 0)
            {
                res = lres + 1;
                break;
            }
        }
    }
    ans = max(ans, res);
    return book[l][r] = res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
            book[i][j] = -1;
    ans = 0;
    dfs(1, n);
    cout << ans;
    return 0;
}