² 博弈取牌—记忆化搜索
题目描述：
有两副带有数字的牌，（数字>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;
}