9.7 滴滴笔试

20选择2编程，已Ak，考试结束放代码

第一题 藏品最大代价，按n的长度分情况讨论即可

第二题 题意：给定长度为n的字符串s（n为偶数，包含小写字母）和一个代价矩阵grid，每次操作可以删除相邻的两个字符并获得代价。求删除所有字符后的最大代价。

思路：区间dp，区间长度初始为2，从小到大递推，并且区间长度始终为偶数。区间[i,j]的代价转移时，要考虑两种情况：第一种，左区间[i, k]和右区间[k + 1, j]合并（此时左右区间信息都有，可以直接推出来），
第二种情况：区间[i, j]由[i + 1, j - 1] + grid[s[i] - 'a'][s[j] - 'a']推过来（这种情况不能直接由子区间转移，是一种特殊的代价及算法方式）
上面两种情况包含了区间[i, j]所有可能的最大代价，直接算就行了