一、区间DP
所谓区间dp，顾名思义就是在一段区间上的动态规划。它既要满足dp问题的最优子结构和无后效性外，还应该符合在区间上操作的特点。我的理解是往往会对区间进行合并操作。抑或是单个元素（可看成一个小区间）跨区间进行操作。例如括号匹配问题，石子合并问题（通过多次的相邻合并，最后实质上会产生跨区间的合并，如果你把其中的石子看作参考系的话就很容易感觉出来），还有在整数中插入运算符号的问题（利用运算符的优先级以及交换律可看出）
这样以来，如果我们要得知一个大区间的情况，由于它必定是由从多个长度不一的小区间转移而来（转移情况未知），我们可以通过求得多个小区间的情况，从而合并信息，得到大区间。
对于一个长度为n的区间，确定它的子区间需要首尾两个指针，显然子区间数量级为n2，那区间dp的复杂度也就为n2
二、操作的模板
1.石子合并问题
题目描述：
有N堆石子排成一排，每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子的和，经过N-1次合并后成为一堆。求出总的代价最小值。
输入
有多组测试数据，输入到文件结束。
每组测试数据第一行有一个整数n，表示有n堆石子。
接下来的一行有n（0< n <200）个数，分别表示这n堆石子的数目，用空格隔开
输出
输出总代价的最小值，占单独的一行
样例输入
3
1 2 3
7
13 7 8 16 21 4 18
样例输出
9
239题目来自：NYOJ 737
石子合并是经典的区间DP问题。
本题是将相邻两边进行依次合并，求最小的合并值。
dp[i][j]表示以i为起点，j为终点的合并值。
状态转移方程就是遍历寻找i与j之间一点，进行更新。
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[i][j]);
1
2
其中sum数组的值就是从i到j所有石子值之和。
开始的时候我以为dp[i][i]应该是该堆石子的值，后面发现这是不对的，应该是0，
因为这一堆没有办法合并，所以最小的合并值就是0.代码如下：
#include<iostream>
#include<stdio.h>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn=210;
int dp[maxn][maxn];
int sum[maxn];
int a[maxn];
int main()
{
int n;
while(~scanf("%d",&n))
{
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i];
}
for(int len=1;len<n;len++)//操作区间的长度
{
for(int i=1,j=len+1;j<=n;i++,j++)//始末
{//检查是否匹配（非必须）
dp[i][j]=INF;
for(int s=i;s<j;s++)
{
dp[i][j]=min(dp[i][j],dp[i][s]+dp[s+1][j]+sum[j]-sum[i-1]);
}
}
}
printf("%d
",dp[1][n]);
}
return 0;
}
2. 括号匹配
Brackets
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 5484 Accepted: 2946
Description
We give the following inductive definition of a “regular brackets” sequence:
the empty sequence is a regular brackets sequence,
if s is a regular brackets sequence, then (s) and [s] are regular brackets sequences, and
if a and b are regular brackets sequences, then ab is a regular brackets sequence.
no other sequence is a regular brackets sequence
For instance, all of the following character sequences are regular brackets sequences:
(), [], (()), ()[], ()[()]
while the following character sequences are not:
(, ], )(, ([)], ([(]
Given a brackets sequence of characters a1a2 … an, your goal is to find the length of the longest regular brackets sequence that is a subsequence of s. That is, you wish to find the largest m such that for indices i1, i2, …, im where 1 ≤ i1 < i2 < … < im ≤ n, ai1ai2 … aim is a regular brackets sequence.
Given the initial sequence ([([]])], the longest regular brackets subsequence is [([])].
Input
The input test file will contain multiple test cases. Each input test case consists of a single line containing only the characters (, ), [, and ]; each input test will have length between 1 and 100, inclusive. The end-of-file is marked by a line containing the word “end” and should not be processed.
Output
For each input case, the program should print the length of the longest possible regular brackets subsequence on a single line.
Sample Input
((()))
()()()
([]])
)[)(
([][][)
endSample Output
6
6
4
0
6Source
Stanford Local 2004
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 105;
char str[maxn];
int dp[maxn][maxn];
bool ck(int i, int j) {
if ((str[i] == '(' && str[j] == ')') || (str[i] == '[' && str[j] == ']')) {
return true;
} else {
return false;
}
}
int main(int argc, const char * argv[]) {
while (~scanf("%s", str)) {
if (str[0] == 'e') break;
int len;
len = strlen(str);
memset(dp, 0, sizeof(dp));
for (int l = 1; l < len; l++) { //len = j - i 为当前区间长度
for (int i = 0, j = l; j < len; i++, j++) { // i++, j++
if (ck(i, j)) { // 匹配
dp[i][j] = dp[i + 1][j - 1] + 2;
}
// 讨论区间合并情况，求最大值
for (int pos = i; pos < j; pos++) {
dp[i][j] = max(dp[i][j], dp[i][pos] + dp[pos + 1][j]);
}
}
}
printf("%d
", dp[0][len - 1]);
}
return 0;
}