设有字符串X，我们称在X的头尾及中间插入任意多个空格后构成的新字符串为X的扩展串，如字符串X为”abcbcd”，则字符串“abcb□cd”，“□a□bcbcd□”和“abcb□cd□”都是X的扩展串，这里“□”代表空格字符。
如果A1是字符串A的扩展串，B1是字符串B的扩展串，A1与B1具有相同的长度，那么我扪定义字符串A1与B1的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定义为它们的ASCII码的差的绝对值，而空格字符与其他任意字符之间的距离为已知的定值K，空格字符与空格字符的距离为0。在字符串A、B的所有扩展串中，必定存在两个等长的扩展串A1、B1，使得A1与B1之间的距离达到最小，我们将这一距离定义为字符串A、B的距离。
请你写一个程序，求出字符串A、B的距离。
对于字符串上的dp，感觉都是很难想，这道题也想了好久没想出来...后来还是问了艾教才将这道题比较理解了。
那么首先先来想dfs，如果考虑dfs，那么可以较为轻松的想到这样的状态dfs(int len1,int len2,int val)表示第一个串考虑到len1,第二个串考虑到len2时的价值为val，那么如果第一个串的len1位与空格匹配了，那么就转移到dfs(len1+1,len2,val+k), 同理如果len2位匹配了，那么就能转移到dfs(len1,len2+1,val+k)，如果两个都匹配成功了，那么就是dfs(len1+1,len2+1,val+abs(s[len1]-t[len2]));
这样从中提取状态也就比较容易了，dp[i][j]表示第一个串考虑到i,第二个串考虑到j时的最小价值，转移也类同与dfs的转移了。所以dp想不出来，想想dfs没准就可以想出答案了。
下附AC代码。
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #define maxn 2005 using namespace std; string s=" "; string t=" "; int dp[maxn][maxn]; int k; int len1,len2; int main() { string temp; cin>>temp; s+=temp; cin>>temp; t+=temp; cin>>k; len1=s.size();len1--; len2=t.size();len2--; memset(dp,0x3f,sizeof(dp)); dp[0][0]=0; for(int i=0;i<=len1;i++) for(int j=0;j<=len2;j++) if(dp[i][j]<87654321) { dp[i+1][j]=min(dp[i+1][j],dp[i][j]+k); dp[i][j+1]=min(dp[i][j+1],dp[i][j]+k); dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]+(int)abs(s[i+1]-t[j+1])); } cout<<dp[len1][len2]<<endl; }
