Brackets

?POJ - 2955? 再明顯不過的區間DP的題目了，要求求出給出符號式中最大匹配的括號數。

考慮區間[l,r]，如果str[l]與str[r]匹配了，那么轉移方程為dp[l][r] = max(dp[l][r],dp[l+1][r-1]+ 2);

然后考慮將區間分成2部分

dp[l][r] = max(dp[l][r],dp[l][k]+dp[k+1][r]);

然后就成了，就這么簡單

#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int MAX = 105; char str[MAX]; int dp[MAX][MAX]; int mp[128]; int main(){mp['('] = ')';mp['['] = ']';while(gets(str)){memset(dp,0,sizeof(dp));if(str[0] == 'e'){break;}int n = strlen(str);for(int k = 2;k <= n;k++){for(int i = 0;i + k <= n;i++){//左閉右開 for(int j = i + 1;j < i + k;j++){dp[i][i+k] = max(dp[i][i + k],dp[i][j] + dp[j][i+k]);if(mp[str[i]] == str[i+k-1])dp[i][i+k] = max(dp[i][i+k],dp[i+1][i+k-1]+2);}} }printf("%d\n",dp[0][n]);}return 0; } /* )[)( */

總結

以上是生活随笔為你收集整理的动态规划训练9 [Brackets POJ - 2955 ]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。