题目：求字符串之间距离 要求：设有字符串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的距离。
思想：这道题目其实可以用一个二维数组来求解的，在分析这道题之前，我想先分析一道用一维数组来借的一道题。
题目的大致意思就是我们手上有3种硬币，面值分别为1元，3元，5元。问怎么用最少的硬币个数来凑11元。
对于这个凑11元，我们可以从最开始的想法来想，假设是凑0元，那么肯定是0个硬币；如果是1元，那么只要一个1元硬币；2元的话2个；3元是1个3元硬币，这个过程又怎么让计算机思考呢？
这就是我今天要说的动态规划（由于我也是小白，只能说点入门的东西），我们让计算机这么想这个问题，先创建一个数组int a[12]（因为我的题目是凑11元，然后后有0-11 12个数字，故取12），a[i]中的i表示的意思凑多少元，a[i]表示凑i元最少的硬币数目，显然a[0]=0 a[1]=1 a[2]=2，对于a[3]我们应该这么想，凑3元有两种方法，第一种是在2元的基础上加一个1元硬币，此时a[3]=a[2]+1;还有一种方法是在0元的基础上加一个3元硬币，此时a[3]=a[0]+1（当然有些人会觉得肯定用3元的时候硬币少啦，这么想肯定是没错的，大家可以看看这个例子，假设这里没有5元硬币的话，我们凑5元的话可以是两元加一个3元硬币3个，也可能是四元加一个1元硬币，都是3个，这里为了逻辑的严密性故给出两种。）。所以这个时候的a[3]应该是上面两种情况中小的那一种，当然当i元大于等于3元的时候也要这么思考，可能是由i-1元加一个1元硬币，也可能是i-3加一个3元硬币，然后在这两种中取小。当然对于5元的硬币思考也是这样的。
具体代码如下
#include<iostream> using namespace std; int q(int i) { int a[i+1]; for(int m=0;m<i+1;m++) { if(m>=5) { a[m]=min(a[m-1]+1,min(a[m-3]+1,a[m-5]+1)); } else if(m>=3) { a[m]=min(a[m-1]+1,a[m-3]+1); } else a[m]=m; } return a[i]; } int main() { cout<<"请问凑多少元："; int n; cin>>n; int m=q(n); cout<<"需要"<<m<<"个硬币"<<endl; return 0; }看完了这个问题我们再回到一开始的这个字符串的问题，对于这个问题，如果我们比较一个n字长和m字长的两个字符串，我们先创建一个二维数组A[n+1][m+1]，我们如果要求A[i][j]的话，下标的意思为第一个前i长度与第二个字符串前m长度的距离最小值，这个问题其实有3种情况：1.可能是A[i-1][j-1]加上第一个字符串的第i位与第二个字符串的第j位的ascll的差值（当前比较的是两个字符）2.可能是A[i-1][j]+k（当前位与空格的差，即当前比较的是一个字符与一个空格）,3.A[i][j-1]+k（当前位与空格的差，即当前比较的是一个字符与一个空格）。
具体代码如下
#include <iostream> #include <string> #include <algorithm> using namespace std; const int N = 2005; char S[N], T[N]; int dp[N][N]; //动态规划问题 int Work(char *S, char *T, int k) { int n = strlen(S); int m = strlen(T); dp[0][0] = 0; for (int i = 1; i <= n; i++) dp[i][0] = i * k; for (int i = 1; i <= m; i++) dp[0][i] = i * k; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) dp[i][j] = min(dp[i - 1][j - 1] + abs(S[i - 1] - T[j - 1]), min(dp[i - 1][j], dp[i][j - 1]) + k); //此处就是动态规划，分为3种情况 return dp[n][m]; } int main() { int k; cout << "请输入第一个字符串数组："; cin >> S; cout << "请输入第二个字符串数组："; cin >> T; cout << "请输入固定的K值："; cin >> k; cout << Work(S, T, k) << endl; return 0; }以上就是我对这个问题的一些看法，谢谢浏览
