POJ 2955 Brackets

题意

给出一个由小括号喝中括号组成的括号序列,定义正规括号序列为(),[],(s),[s],其中s也是正规括号序列。求最长正规括号序列的长度。

思路

考虑区间DP,设计状态时着眼于“最后一次加括号”。

状态表示:dp[i][j] = 从 i 到 j 的(包含i,j)最长的括号序列长度。

状态转移:

  • dp[i][j] = dp[i][j-1] 继承上一个区间的结果
  • 令k为i,j之间的一个位置,str是给出的括号串(令下标从1开始)
  • 如果str[k]与str[j]正好是一对匹配的括号,可以考虑在最后一步放这个括号,用dp[i][k] + 2 + dp[k+1][j-1]尝试更新dp[i][j]

答案:dp[1][len]

初始化:直接令整个dp数组都为0,既可以完成初始化,也可以无效化所有无效状态。

代码

 

1 Comment

  1. […] POJ 2955 Brackets:最简单的区间DP,括号序列 […]

    Reply

Leave a Reply

Scroll to top