poj2955——括号匹配+区间dp经典题-白红宇

poj2955——括号匹配+区间dp经典题

阅读量：656 次

发布时间：2019-03-15

本文共 2161 字，大约阅读时间需要 7 分钟。

为了解决这个问题，我们需要找到给定字符串中最长的常规括号子序列的长度。常规括号序列的定义非常明确，包括空序列、单个括号及其闭合括号，以及由常规序列组成的更长序列。

方法思路

我们可以使用动态规划来解决这个问题。动态规划的状态定义为 dp[i][j]，表示从索引 i 到 j 的子串中能形成的最长常规括号序列的长度。

初始化：当 i > j 时，dp[i][j] 为 0；当 i == j 时，dp[i][j] 也是 0，因为单个字符无法形成括号。

状态转移：

如果 s[i] 和 s[j] 是一对匹配的括号（即 s[i] 是 '(' 而 s[j] 是 ')'，或者 s[i] 是 '[' 而 s[j] 是 ']'），那么 dp[i][j] = dp[i+1][j-1] + 2。

另外，我们需要考虑分割点 k，即从 i 到 k 和从 k+1 到 j 的最长子序列之和，并取最大值。

解决代码

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;int main() {    char str[1005];    int n;    while (scanf("%s", str+1) != EOF && strcmp(str+1, "end") != 0) {        n = strlen(str+1);        int dp[n+2][n+2];        for (int i = 0; i <= n; ++i) {            for (int j = 0; j <= n; ++j) {                dp[i][j] = 0;            }        }        for (int len = 2; len <= n; ++len) {            for (int i = 1; i <= n - len + 1; ++i) {                int j = i + len - 1;                bool is_open = (str[i] == '(' || str[i] == '[');                bool is_close = (str[j] == ')' || str[j] == ']');                if (is_open && is_close) {                    int option1 = dp[i+1][j-1];                    option1 += 2;                    if (option1 > dp[i][j]) {                        dp[i][j] = option1;                    }                    for (int k = i; k < j; ++k) {                        int option2 = dp[i][k] + dp[k+1][j];                        if (option2 > dp[i][j]) {                            dp[i][j] = option2;                        }                    }                } else {                    for (int k = i; k < j; ++k) {                        int option2 = dp[i][k] + dp[k+1][j];                        if (option2 > dp[i][j]) {                            dp[i][j] = option2;                        }                    }                }            }        }        cout << dp[1][n] << endl;    }    return 0;}

代码解释

读取输入：从标准输入读取字符串，直到遇到 "end" 为止。

初始化动态规划表：创建一个 dp 表，大小为 (n+2) x (n+2)，初始值为 0。

填充动态规划表：

遍历所有可能的子串长度 len。

对于每个子串起始位置 i，计算结束位置 j。

检查 s[i] 和 s[j] 是否为匹配的括号对，如果是，计算包含这对括号的子序列长度。

考虑分割点 k，找出从 i 到 k 和从 k+1 到 j 的最长子序列之和。

输出结果：打印 dp[1][n]，即整个字符串的最长常规括号子序列长度。

转载地址：http://vifmz.baihongyu.com/

你可能感兴趣的文章