Cheapest Palindrome

这个区间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.cnblogs.com/sos3210/p/12308481.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有