区间DP

区间DP

区间DP常用模板
所谓区间DP，指在一段区间上进行动态规划，一般做法是由长度较小的区间往长度较大的区间进行递推，最终得到整个区间的答案，边界就是长度为1和2的区间

所有的区间DP问题，有两种写法
1、第一维都是枚举区间长度，第二维枚举起点，先求出小区间的属性值，进而扩展到大区间
核心思想：小区间 ---> 大区间

for (int i = 1; i <= n; i++) {
    dp[i][i] = 初始值
}
for (int len = 2; len <= n; len++)           //区间长度
    for (int i = 1; i + len - 1 <= n; i++) { //枚举起点
        int j = i + len - 1;                 //区间终点
        for (int k = i; k < j; k++) {        //枚举分割点，构造状态转移方程
            dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]);
        }
    }

2、第一维从最尾部开始枚举起点，第二维枚举终点(从短到长)

for(int i = n;i >= 1;i--) { // 起点从尾部开始
  dp[i][i] = 初始值;
  for(int j = i + 1;j <= n;j++) { // 终点
    f[i][j] = max(.......)
  }
}

1、区间DP复习

2、石子合并

3、PKUpoj3280

题目描述：给定一个字符串，通过增加或删除相关字母形成回文串，每一个不同的字母增加和删除操作需要的花费不同，求形成回文串所需的最小代价

思路

#include 
#include 
#include 
#include 
using namespace std;
const int N = 2010;
char s[N];
int n, m;
int cost[30];
int dp[N][N];//dp[i][j] 存储从 i 到 j 这一段转换成回文子序列需要的最小花费

int main() {
	ios::sync_with_stdio(false);//将stdio解除绑定,使得cin与scanf效率相差无几
	int a, b;
	char t;
	while (cin >> n >> m) {
		cin >> s + 1;
		while (n--) {
			cin >> t >> a >> b;
			cost[t - 'a'] = min(a, b);
		}
//		for (int i = m; i >= 1; i--) {
//			dp[i][i] = 0;
//			for (int j = i + 1; j <= m; j++) {
//				if (s[i] == s[j]) {
//					if (j - i <= 2)
//						dp[i][j] = 0;
//					else
//						dp[i][j] = dp[i + 1][j - 1];
//				} else
//					dp[i][j] = min(dp[i + 1][j] + cost[s[i] - 'a'], dp[i][j - 1] + cost[s[j] - 'a']);
//			}
//		}
		for (int i = 1; i <= m; i++)
			dp[i][i] = 0;
		for (int len = 2; len <= m; len++) // 长度,从短到长
			for (int i = 1; i + len - 1 <= m; i++) { // 起点
				int j = i + len - 1; // 终点
				if (s[i] == s[j]) {
					if (j - i <= 2)
						dp[i][j] = 0;
					else
						dp[i][j] = dp[i + 1][j - 1];
				} else {
					if (j - i <= 1)
						dp[i][j] = min(cost[s[i] - 'a'], cost[s[j] - 'a']);
					else
						dp[i][j] = min(dp[i + 1][j] + cost[s[i] - 'a'], dp[i][j - 1] + cost[s[j] - 'a']);
				}
			}

		printf("%d\n", dp[1][m]);
	}
	return 0;
}
关于起点从尾部开始递推的写法的原因
`dp[i][j] = min(dp[i+1][j], dp[i][j-1])`
由于`dp[i][i]`起点是i，而它是由起点 i + 1比较得来的，所以可以从尾部开始，那么第二层循环就是遍历长度(防止越界)

4、括号配对
题意：给出一串括号，要求输出添加括号最少，并使所有括号均有匹配的串
思路：
状态表示：dp[l][r]表示向字符串中的i~j变成匹配的串的最少添加数量
状态计算：1、l与r匹配,dp[l][r] = dp[l+1][r-1],举个例子比如：[]([],如果直接按照前面这样计算dp[l][r],]([的结果为3，但是实际答案却是1。可以先匹配[] + ([],也就是f[1,2]+f[3,5]。
遍历该区间的子区间，看是否有匹配的括号串，从而减少答案。dp[l][r] = dp[l][k] + dp[k+1][r]。

#include 
#include 
#include 
#include 
using namespace std;

const int N = 110, inf = 0x3f3f3f3f;

char s[N];
int f[N][N]; // f[i][j]代表将i~j个字符变成GBE的所有方案的集合的最小值

bool check(int a, int b)
{
    if (s[a] == '[' && s[b] == ']' || s[a] == '(' && s[b] ==')') return true;
    return false;
}

int main()
{
    scanf("%s", s + 1);
    int n = strlen(s + 1);

    for (int len = 1; len <= n; len++)
        for (int l = 1; l + len - 1 <= n; l++)
        {
            int r = l + len - 1;
            if (len == 1) f[l][r] = 1;
            else
            {
                f[l][r] = inf;
                if (check(l, r)) f[l][r] = min(f[l][r], f[l + 1][r - 1]);
                for (int k = l; k < r; k++)
                    f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r]);
            }
        }

    cout << f[1][n] << endl;

    return 0;
}

附：记录输出最终的答案
pos[i][j] = k表示括号串i-j中以第k个位置分开使得两部分匹配
pos[i][j] == -1表示i和j两端点匹配