区间DP学习笔记

区间DP定义

顾名思义：区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个大区间上最优解的dp算法。

实现思路

• 既然是在区间里进行DP：
• 以‘区间长度’作为阶段
• 状态为某区间内的最有解，即将长度为1的元区间作为DP的最小状态。使用 $dp[l,r]$dp[l,r] 描述每一个维度。

典型例题

删除字符串

题目描述

给出一个长度为n的字符串，每次可以删除一个字母相同的子串，问最少需要删多少次。 数据规模：n <= 500

输入格式

第1行：1个整数，表示字符串的长度
第2行：n个字符的字符串

输出格式

第1行：1个整数，表示答案

样例

样例输入

5
$abaca$abaca

样例输出

3

样例解释：

step 1：删除 $b$b 得到

$aaca$aaca

step 2 : 删除 $c$c 得到

$aaa$aaa

step 3 : 因为 $aaa$aaa 为相同的子串，既可以一次删除。

$空串$空串

分析

此题即为典型的区间DP题，根据题目可以设以 $dp[l,r]$dp[l,r] 是为 $l$l 到 $r$r 区间删除完字符串的最小次数，可分两种情况讨论：

• 一般情况下， $dp[l,r]$dp[l,r] 由长度可以通过 $dp[l+1,r]$dp[l+1,r] 或 $dp[l,r-1]$dp[l,r−1]增加一个字符得到，此时取两者之间的最小值。
• 枚举 $k\in (l,r)$k∈(l,r)， 用 $k$k 作为决策点，如果 $c\left[l\right]=c\left[k\right]$c[l]=c[k] 即可以通过 $dp\left[l\right][k-1]+dp\left[k\right]\left[r\right]$dp[l][k−1]+dp[k][r]直接得到， 注意此处不需要加一， 因为 $c\left[l\right]$c[l] 和 $c\left[k\right]$c[k]是相同字符，所以可以直接删除，而在计算 $c\left[l\right]$c[l] 和 $c\left[k\right]$c[k]时，已经加一所以，不需要加一！

不难得到状态转移方程：

• 一般情况：
  $dp\left[l\right]\left[r\right]=min\left(dp\right[l+1\left]\right[r]+1,dp[l\left]\right[r-1]+1);$dp[l][r]=min(dp[l+1][r]+1,dp[l][r−1]+1);
• $k\in (l,r)$k∈(l,r)， 如果 $c\left[l\right]=c\left[k\right]$c[l]=c[k] ：
  $dp\left[l\right]\left[r\right]=min\left(dp\right[l\left]\right[r],dp[l\left]\right[k-1]+dp[k\left]\right[r\left]\right);$dp[l][r]=min(dp[l][r],dp[l][k−1]+dp[k][r]);

AC代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int n, dp[505][505];
char c[505];

int main() {
    scanf("%d", &n);
    scanf("%s", c + 1);//从一号位开始存
    // for(int i = 1;i <= n; i++) {
    // printf("%c", c[i]);
    // }
    memset(dp, 0x3f, sizeof(dp));//初始化
    for (int i = 1; i <= n; i++) dp[i][i] = 0;
    for (int len = 2; len <= n; len++) {//阶段 len -> 长度
        for (int l = 1; l <= n - len + 1; l++) {//状态 l -> 左端点
            int r = l + len - 1;//状态 r -> 右端点
            dp[l][r] = min(dp[l + 1][r] + 1, dp[l][r - 1] + 1);//一般情况
            for (int k = l; k <= r; k++) {//决策 k -> 划分点
                if (c[l] == c[k])//字符相同
                    dp[l][r] = min(dp[l][r], dp[l][k - 1] + dp[k][r]);
            }
        }
    }
    printf("%d\n", dp[1][n] + 1);
    return 0;
}

注意

区间DP的循环顺序应该为

for(阶段)
	for(状态)
		for(决策)