「区间DP-步入」括号匹配（超详细的）

题目描述

给出一个括号序列，求其中匹配的括号数。

输入

一个整数，表示序列长度。

一串括号序列。

输出

一个整数，表示答案。

样例

7
([][][)

6

说明

• http://poj.org/problem?id=2955

分析

首先，咱们缩小问题规模：求一段小区间内的括号匹配数

()   // 1
(()  // 1
())  // 1
((]) // 1
(()) // 2

由此可见，其右括号的位置是不固定的。

既然右括号位置不固定，那么我们就以 len 从递增对序列进行分割。

[()]
0123

根据上面的这个例子，假设中括号内的括号序列已经求出来了，为 2，最后加上 2 即可。

所以当 [0] == [3] ，已知 [1][2] = 2 时，[0][3] = [1][2] + 2

(())
0123

所以当 [0] != [3] ，已知 [1][2] = 2 时，[0][3] = [1][2]

([][]
01234

还需要注意，当 [0] != [4] ，已知 [1][3] = 2，[1][2] = 2 时，此时用之前的方法 [0][4] = [1][3] 结果为 2，这样是行不通的，因此需要枚举每一个断点 k，枚举断点 k 的过程如下：

已知 [0,2] = 2 和 [0,3] = 2 和 [1,2] = 2 和 [1,3] = 2 和 [1,4] = 4 和 [2,4] = 2 和 [3,4] = 2
k = 0, [0,0] + [1,4] = 0 + 4 = 4
k = 1, [0,1] + [2,4] = 0 + 2 = 2
k = 2, [0,2] + [3,4] = 2 + 2 = 4
k = 3, [0,3] + [4,4] = 2 + 0 = 2

观察枚举断点 k 的过程可发现所切割出来的区间都是之间以 len 分割的区间，这些区间都是已知的括号匹配数，最后取最大值即可。

因此每次都需要枚举断点 k。可得方程：
$$dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j])$$
DP 信息：

• 原问题：求的括号匹配数
• 子问题：求 [i][j] 的括号匹配数
• DP 定义：求 [i][j] 的括号匹配数
• DP 方程：$dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j])$
• DP 边界：无

代码

public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();sc.nextLine();char[] arr = (sc.nextLine() + " ").toCharArray();int[][] dp = new int[n][n];for(int len = 2; len <= n; len++) { // 枚举区间长度for(int i = 0; i + len - 1 < n; i++) { // 枚举区间起点int j = i + len - 1; // 计算区间终点if((arr[i] == '(' && arr[j] == ')') || (arr[i] == '[' && arr[j] == ']')) {dp[i][j] = dp[i+1][j-1] + 2;} else {dp[i][j] = dp[i+1][j-1];}//System.out.printf("len = %d [%d,%d]\\n", len, i, j);for(int k = i; k < j; k++) { // 枚举分界点dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k+1][j]);//System.out.printf("  k = %d [%d,%d] [%d,%d]\\n", k, i, k, k+1, j);}//System.out.println("====================");}}System.out.println(dp[0][n-1]);}
}