這個區間dp解的話是先知道小區間再推大區間，具體需要分類討論當小區間已經是回文串了，下一層判斷，所以一層一個呢還是一層兩個呢，
下面討論一層一個的話是什么情況，那么如果一層兩個，可以在評論區寫下代碼供大家參考（謝謝貢獻~嘿嘿）
那么，首先要考慮長度為一，那么不需要任何花費，（這就是邊界條件了）
之后的話，找到共性，如果新加入的那個等于另一端的那個，那么dp[i][j]=dp[i+1][j-1];（這個總花費便等于它兩端沒有這兩相同字符的總花費）（對了，這里i是串首，j是串尾）
如果新加入的這這個字符不等于另一端的那個字符的話，便是看它的子區間（沒有左端的，或者沒有右端的）那個更大，畢竟假設i~j的長度為l，那么l-1的區間已經遍歷過了，所以狀態轉移方程為dp[i][j]=min(dp[i][j-1]+price[str[j]-'a'],dp[i+1][j]+price[str[i]-'a']);（str為字串）
接下來考慮順序，因為大區間需要小區間的結果，所以它的小區間遍歷過了，才能輪到它
那么到這里寫代碼
我的方法只是我想到的一種（因為太懶了，復雜度相同的代碼遍一次就夠了），大家可以按照理解自行解決
我的代碼如下：
#include <iostream>
#include <string>
using namespace std;
int n,price[30],m,dp[2001][2001],in,put;
int main()
{
char ch;
string str;
cin >> n >> m;
cin >>str;
for(int i=0;i<n;i++){
cin >> ch >> in >> put;
price[ch-'a']=min(in,put);
}
for(int i=m-1;i>=0;i--){
for(int j=i+1;j<m;j++){
if(str[i]==str[j]){
dp[i][j]=dp[i+1][j-1];
}
else{
dp[i][j]=min(dp[i][j-1]+price[str[j]-'a'],dp[i+1][j]+price[str[i]-'a']);
}
}
}
cout << dp[0][m-1] << endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/63266.html
標籤：C++