考虑对于区间$[l,r]$， Bob是否可以达成平手。

如果Alice取$l$，Bob取$r$并且有$s[l]=s[r]$，那么区间就转移到了$[l+1,r-1]$上。相反的，如果Alice取$r$，那么Bob可以取$l$，也是同上的。

如果Alice取$l$，Bob取$l+1$并且有$s[l]=s[l+1]$，那么区间就转移到$[l+2,r]$上。值得注意的是，如果这种取法如果可以达成平局，那么Alice就不会取$l$，而是会选择取$r$，那么同理就转移到$[l,r-2]$上。所以对这类取法，返回的应该是两种结果的与。

dp写法

#include <bits/stdc++.h>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define lowbit(x) (x&(-x))

#define fi first
#define se second
#define SZ(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;

using ll=long long;

ll tt,n;
char s[2009];
int f[2009][2009];
map<char,vi> wz;

bool ck(){
	for(int r=2;r<=n;++r){
		for(int l=r-1;l;--l){
			if(l+1==r)f[l][r]=s[l]==s[r];
			else{
				bool f1=false,f2=false;
				if(s[l]==s[r]&&f[l+1][r-1])f1=f2=true;
				if(s[l+1]==s[l]&&f[l+2][r])f1=true;
				if(f[l][r-2]&&s[r-1]==s[r])f2=true;
				f[l][r]=f1&f2;
			}
		}
	}
	return f[1][n];
}


int main()
{
    scanf("%lld",&tt);
    f(sb,1,tt){
    	wz.clear();
    	scanf("%s",s+1);
    	n=strlen(s+1);
    	for(int i=1;i<=n;++i)wz[s[i]].push_back(i);
    	if(ck()){cout<<"Draw\n";}
    	else cout<<"Alice\n";
    }
    return 0;
}

记忆化搜索写法：

#include <bits/stdc++.h>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define lowbit(x) (x&(-x))

#define fi first
#define se second
#define SZ(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;

using ll=long long;

int tt,n,f[2009][2009];
char s[2009];

bool dfs(int l,int r){
    if(l+1==r)return s[l]==s[r];
    if(~f[l][r])return f[l][r];
    bool f1=false,f2=false,f3=false;
    if(s[l]==s[l+1])f1=dfs(l+2,r);
    if(s[l]==s[r])f2=dfs(l+1,r-1);
    if(s[r]==s[r-1])f3=dfs(l,r-2);
    return f[l][r]=(f1&f3)|f2;
}

int main()
{
    scanf("%d",&tt);
    for(int i=1;i<=tt;++i){
        scanf("%s",s+1);
        n=strlen(s+1);
        for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)f[i][j]=-1;
        printf("%s",dfs(1,n)?"Draw\n":"Alice\n");
    }
    return 0;
}