1.题目

算法分析与设计作业——
对于长度相同的2个字符串A和B，其距离定义为相应位置字符距离之和。2个非空格字符的距离是它们的ASCII码之差的绝对值。空格与空格的距离为0，空格与其他字符的距离为一定值k。
在一般情况下，字符串A和B的长度不一定相同。字符串A的扩展是在A中插入若干空格字符所产生的字符串。在字符串A和B的所有长度相同的扩展中，有一对距离最小的扩展，该距离称为字符串A和B的扩展距离。
算法要求如下
1、 数据输入：第1行是字符串A，第2行是字符串B，第3行是空格与其他字符的距离定值k。
2、 输出：字符串A和B的扩展距离。
例如
输入：
cmc
snmn
2
输出：10

2.思路

转移方程：val[i][j]=min(val[i-1][j]+k,val[i][j-1]+k,val[i-1][j-1]+abs(A[i-1]-B[j-1])
min(A串当前位用空格填充，B串当前位用空格填充，不用空格填充)
初始状态:val[0][x],val[x][0]=t*x;
对于空串和另一个非空串，空串全部用空格填充，扩展距离是非空串的长度 *定值k。

3.代码

public class Solution {
    public static void main(String[] args) {
        String a="cmc";
        String b="snmn";
        int k=2;

        char[] A=a.toCharArray();
        char[] B=b.toCharArray();
        int res=count(A,B,k);
        System.out.println(res);
    }
    public static int count(char[] A,char[] B,int k){
        int len1=A.length+1;
        int len2=B.length+1;
        int[][] val=new int[len1][len2];
        for(int t1=1;t1<len2;t1++){
            val[0][t1]=k*t1;
        }
        for(int t2=1;t2<len1;t2++){
            val[t2][0]=k*t2;
        }
        for(int i=1;i<len1;i++){
            for(int j=1;j<len2;j++){
                val[i][j]=Math.min(
                        Math.min(val[i-1][j]+k,val[i][j-1]+k),
                        val[i-1][j-1]+Math.abs(A[i-1]-B[j-1]));
            }
        }
        return val[len1-1][len2-1];
    }
}

4.结果