问题描述
对于长度相同的两个字符串 A 和 B，其距离定义为相应位置字符距离之和。两个非空格字符的距离是它们的 ASCII 编码之差的绝对值。空格与空格的距离为 0，空格与其他字符的距离为一定值 k。

在一般情况下，字符串 A 和 B 的长度不一定相同。字符串 A 的扩展是在 A 中插入若干空格字符产生的字符串。在字符串 A 和 B 的所有长度相同的扩展中，有一对距离最小的扩展，该距离称为字符串 A 和 B 的扩展距离。

算法设计
对于给定的字符串 A 和 B，试设计一个算法，计算其扩展距离。

数据输入

输入文件 input.txt 给出输入数据。第 1 行是字符串 A，第 2 行是字符串 B，第 3 行是空格与其他字符的距离定值 k。

结果输出
将计算出的字符串 A 和 B 的扩展距离输出到文件 output.txt。

input.txt
cmc
snmn
2

output.txt
10

#include 
#include
using namespace std;

/*
cmc
snmn
2
动态规划，拥有最优子结构，设数组dp[i][j]表示str1的前i个字符和str2的前j个字符的距离最小值（i<=m,j<=n) 
dp[i][j]可以由三种情况转换而来 
1、str1的第i个字符前加空格，str2不加空格，则dp[i][j] = dp[i][j-1]+k；加了空格之后，想对于原字符串，str2消耗了一个字符，str1没消耗，因此是从dp[i][j-1]转移过来 
2、str1不加空格，str2的第j个字符前加空格，则dp[i][j] = dp[i-1][j]+k；同上 
3、str1和str2都不加空格，则dp[i][j] = dp[i-1][j-1]+dist(str1[i],str2[j])；两个字符串都会消耗一个字符，因此是从dp[i-1][j-1]转移过来 
4、都加空格没有意义 
*/ 

string str1, str2; int k;//空格与其他字符的距离 
int dis(char c1, char c2){//计算两个字符之间的距离 
    return abs(c1-c2); 
} 
int get_min(int a, int b, int c, int d){//获取四个值中的最小值 
    return min(a,min(b,min(c,d))); 
} 
void solve(){ 
    cin>>str1>>str2>>k;
    int m = str1.length(), n = str2.length();
    int dp[m+1][n+1];//dp[i][j]表示str1的前i个字符和str2的前j个字符的距离最小值

    for(int i=0;i<=m;i++){
        for(int j=0;j<=n;j++){
            //特殊处理两个字符为空的情况
            if(i==0 && j==0) {
                dp[i][j] = 0; 
                continue;
            }
            //特殊处理某一字符为空的情况
            if(i==0||j==0){
                //直接将空字符按空格填满
                dp[i][j] = k*(i+j);
                continue;
            }
            dp[i][j] = 1e9;
            dp[i][j] = get_min(dp[i][j], dp[i-1][j]+k, dp[i][j-1]+k, dp[i-1][j-1]+dis(str1[i-1],str2[j-1]));
        }
    }
    cout<<dp[m][n]<<endl;
}
int main(){
    solve();
    return 0;
}