² 博弈取牌—记忆化搜索

题目描述：

有两副带有数字的牌，（数字>0）两人轮流取，取中了某张牌，自己的分数就加上牌上的数字，但只能从两端取，每人都会用最优的策略使得自己的分数最高。问A先取，他能得到的最高的分数。

解法：

记忆化搜索，对于第一、二副牌的左右端点分别为fr1,ta1, fr2,的情形，某个人能拿到的分数的最大值这次取走牌fr1,ta1,fr2,ta2中的最大值，牌的数目减1，问题规模被缩小。边界条件为当没有牌时为0。因为两个人都是这么思考，可抽象成一个人。当总分数为sum时，我能得到的分数会是sum-对手能拿到的分数。

代码实现：

int dp[N][N][N][N]; //初始值为0

int a[N],b[N];//记录第一副牌和第二副牌

//sum的初始值为总值

int dfs(int fr1,int ta1,int fr2,int ta2,int sum)

{

if(fr1>ta1 && fr2>ta2) return 0;

if(dp[fr1][ta1][fr2][ta2]) return dp[fr1][ta1][fr2][ta2];//已经被搜到过

int m =0;    //以下是四种决策

if(fr1 <= ta1)

{//总的钱数-对手能拿到的最多的钱数，下同

m = max(m,sum-dfs(fr1+1,ta1,fr2,ta2,sum-a[fr1]));

m = max(m,sum-dfs(fr1,ta1-1,fr2,ta2,sum-a[ta1]));

}

if(fr2 <= ta2)

{

m = max(m,sum-dfs(fr1,ta1,fr2+1,ta2,sum-b[fr2]));

m = max(m,sum-dfs(fr1,ta1,fr2,ta2-1,sum-b[ta2]));

}

return dp[fr1][ta1][fr2][ta2] = m;

}