AcWing 4997. 更小的数(dfs+记忆化搜索)
原题链接
中等
#include <bits/stdc++.h>
using namespace std;
const int N = 5e3+10;
string a;
int ans;
int f[N][N]; //记录从i到j是否是一种正确的方案
int dfs(int i, int j)
{
if (f[i][j]!=-1) return f[i][j]; //之前已经记录过
if (a[i]>a[j]) return f[i][j] = 1;
if (a[i]<a[j]) return f[i][j] = 0;
if (a[i]==a[j])
{
if (i==j+1 || i==j)
{
return f[i][j] = 0;
}
else
{
return f[i+1][j-1] = dfs(i+1,j-1);
}
}
}
int main()
{
memset(f, -1, sizeof f);
cin >> a;
for (int i=0; i<a.length()-1; i++)
{
for (int j=i+1; j<a.length(); j++)
{
ans += dfs(i,j);
}
}
cout << ans;
return 0;
}