间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的最优解进而得出整个大区间上最优解的 dp 算法。
既然让我求解在一个区间上的最优解，那么我把这个区间分割成一个个小区间，求解每个小区间的最优解，再合并小区间得到大区间即可。
所以在代码实现上，我可以枚举区间长度len为每次分割成的小区间长度（由短到长不断合并），内层枚举该长度下可以的起点，自然终点也就明了了。然后在这个起点终点之间枚举分割点，求解这段小区间在某个分割点下的最优解。
可能性展开的常见方式：
1.基于两侧端点讨论的可能性展开
2.基于范围上划分点的可能性展开
基于两侧端点讨论的可能性题目
题目一
暴力解法：
直接采用递归的方法，对两侧端点进行讨论，取min
int cmp(char* s, int r, int l)
{
if (r == l) //如果只有一个字符
return 0;
if (r + 1 == l) //如果只有两个字符
{
if (s[r] == s[l])
return 0;
else
return 1;
}
if (s[r] == s[l]) // 如果两个端点的字符相同
return cmp(s, l+1, r-1);
else
return min(cmp(s, l+1, r)+1, cmp(s, l, r-1)+1);
}
当两个端点的字符不相同时，例如aab，我们有两种方式进行插入，我们先满足 l 位置与后面的位置相同，也就是在 b 的后面插入 a 时，那下一步的 r 保持不变，l + 1，当我们也可以满足 r 位置与前面的位置相同，也就是在 a 的前面插入 b 时，则下一步的 l 保持不变，r - 1
两个操作都加一，取最小值。
暴力的递归的方法递归层数太多，那我们就可以通过记忆化搜索
优化一
int f2(char* s, int l, int r, int (*dp)[10])
{
if (dp[l][r] != -1)
return dp[l][r]
int ans;
if (l == r)
{
ans = 0;
}
else if (l + 1 == r)
{
if (s[l] = s[r])
{
ans = 0;
}
else
{
ans = 1;
}
}
else
{
if (s[l] == s[r])
ans = f2(s, l+1, r-1, dp);
else
ans = min(f2(s, l+1, r, dp), f2(s, l, r-1, dp)) + 1;
}
dp[l][r] = ans;
return ans;
}也可以分析其严格依赖位置的动态规划
（分析可变参数的范围）
假设这个字符串长度为 5
那么我们就可以做出它的二维dp表（dp[i][j] 表示从 i 到 j 保持回文的最小操作次数）
因为 l 一定小于 r
所以它的表为：
当l == r的时候，操作次数一定为0
当l + 1 == r时
我们也可以直接求出对应的dp值
最终，我们要求的就是最右上角的格子（也就是dp[4][4]）
那我们分析dp[i][j] 的位置依赖
从递归可知：
dp[i][j] 是由 dp[i+1][j-1]，dp[i+1][j]，dp[i][j-1] 三个位置得到
因此我们可以发现要求出dp[ i ][ j ]就必须先求出dp[ i+1 ][ j-1 ]，dp[ i+1 ][ j ]，dp[ i ][ j-1 ]
所以我们的求解顺序：
所以我们就可以直接求出dp表
# include <stdio.h>
int main()
{
char s[10];
int dp[10][10]; //表示从i到j位置保持回文的最少操作次数
int n = 10; //字符串长度
for (int i=0; i<n-1; ++i)
{
if (s[i] == s[i+1])
dp[i][i+1] = 0;
else
dp[i][i+1] = 1;
}
for (int l=n-3; l>=0; --l) //从小到上
for (int r = l+2; r<n; ++r) //从左到右
{
if (s[l] == s[r])
dp[l][r] = dp[l+1][r-1];
else
dp[l][r] = min(dp[l][r-1], dp[l+1][r]);
}
}也可以用一维dp优化空间
代码类似
题目二
暴力递归：
# include <stdio.h>
//考虑num[l …r]范围上的数字进行游戏，轮到玩家1
//返回玩家1最终能获得多少分数，玩家1和玩家2都绝顶聪明
int cmp(int* num, int l, int r)
{
if (l == r)
return num[l];
if (l + 1 == r )
return max(num[l], num[r]);
//当玩家1，拿num[l]后，轮到玩家2了，他考虑num[l+1, r]，因为两个人都是
//顶聪明，所以玩家2一定拿max(num[l+1], num[r])，然后轮到玩家1面对的情况
//一定是 min(cmp(num, l+2, r), cmp(num, l+1, r-1))
int p1 = num[l] + min(cmp(num, l+2, r), cmp(num, l+1, r-1));
//当玩家1，拿num[r]后 …
int p2 = num[r] + min(cmp(num, l+1, r-1), cmp(num, l, r-2));
return max(p1, p2);
}
int main()
{
int sum = 0;
int num[10];
for (int i=0; i<10; ++i)
{
scanf("%d", &num[i]);
sum = sum + num[i];
}
int n = 10;
int first = cmp(num, 0, n-1); //玩家1
int second = sum - first; //玩家2
} 记忆化搜索
# include <stdio.h>
int dp[10][10];
//考虑num[l …r]范围上的数字进行游戏，轮到玩家1
//返回玩家1最终能获得多少分数，玩家1和玩家2都绝顶聪明
int cmp(int* num, int l, int r)
{
int ans;
if (dp[l][r] != -1)
return dp[l][r];
if (l + 1 == r )
ans = max(num[l], num[r]);
else
{
int p1 = num[l] + min(cmp(num, l+2, r), cmp(num, l+1, r-1));
int p2 = num[r] + min(cmp(num, l+1, r-1), cmp(num, l, r-2));
ans = max(p1, p2);
}
return ans;
}
int main()
{
memset(dp, -1, sizeof(dp));
int sum = 0;
int num[10];
for (int i=0; i<10; ++i)
{
scanf("%d", &num[i]);
sum = sum + num[i];
}
int n = 10;
int first = cmp(num, 0, n-1); //玩家1
int second = sum - first; //玩家2
} 也可以分析其严格依赖位置的动态规划
（分析可变参数的范围）
dp[i][j] 是由 dp[i + 2][j], dp[l+1][r - 1], dp[l][r-2]得到
代码于上题类似
