poj 2955 Brackets 區間dp

poj 2955 Brackets 區間dp

題目大意是給你一個字符串，字符串由中括號和小括號組成，問該串裡的最長的一個符合數學括號匹配規范的子序列是多長。

一開始打算用傳說中的左閉右開區間來寫，後來發現果然不適合我，還是換回左閉右閉區間寫了。

dp的思路比較簡單，dp[i][j] 表示從 i 到 j 的串種符合括號匹配的最長子序列。對於任意一個區間均可以存在一個點k (i <= k < j) 把區間分成 [i, k] 和 [k+1, j] 兩部分。

所以得轉移方程： dp[i][j] = max (dp[i][k] + dp[k+1][j])

另外，如果 i 和 j 的括號匹配的話,這裡又多了一種情況，即 dp[i][j] = max (dp[i-1][j+1] + 2)

然後記憶化就行了。(感覺這種題目還是要記憶化更有感覺)

#include 
#include 
#include 
using namespace std;

string a;

int dp[101][101];

bool judge(char a, char b) {
    if (a == '(' && b == ')') return true;
    if (a == '[' && b == ']') return true;
    return false;
}

int DP(int l, int r) {
    if (dp[l][r] != -1) {
        return dp[l][r];
    }www.Bkjia.com

    if (l == r) {
        return dp[l][r] = 0;
    }

    int tmp = 0;

    for (int k=l; k> a) {
        if (a == end) break;

        memset(dp, -1, sizeof(dp));

        int ans = DP(0, a.size()-1);

        cout << ans << endl;
    }
    return 0;
}