问题：
对于长度相同的2个字符串A和B，其距离定义为相应位置字符距离之和。2个非空格字符的距离是它们的ASCII码之差的绝对值；空格与空格的距离为0，空格与其他字符的距离为一个定值k。在一般情况下，字符串A和B的长度不一定相同。字符串A的扩展是在A中插入若干空格字符所产生的字符串。在字符串A和B的所有长度相同的扩展中，有一对距离最短的扩展，该距离称为字符串A和B的扩展距离。对于给定的字符串A和B，设计一个算法，计算其扩展距离。
测试数据：
输入：cmc snmn 2 （分别表示字符串A、B和定值k）
输出：10
输入：cdd snmn 1 （分别表示字符串A、B和定值k）
输出：7
输入：cd ad 1 （分别表示字符串A、B和定值k）
输出：2
//当场没做出来,汗颜啊
//回来查了下,原来是动态规划
//JAVA实现了一下:
import static java.lang.Math.abs;
import static java.lang.Math.min;
public class DPString {
public static int MAX_LEN = 2014;
public static int work(char str1[], char str2[], int k) {
int[][] dp = new int[MAX_LEN][MAX_LEN];
int length1 = str1.length;
int length2 = str2.length;
dp[0][0] = 0;
for (int i = 1; i <= length1; i++) {
dp[i][0] = i * k;
}
for (int i = 1; i <= length2; i++) {
dp[0][i] = i * k;
}
for (int i = 1; i <= length1; i++) {
for (int j = 1; j <= length2; j++) {
dp[i][j] = min(dp[i - 1][j - 1] + abs(str1[i - 1] - str2[j - 1]), min(dp[i - 1][j], dp[i][j - 1]) + k);
}
}
return dp[length1][length2];
}
public static void main(String[] args) {
String stra = "cdd";
String strb = "snmn";
int k = 1;
System.out.println(work(stra.toCharArray(), strb.toCharArray(), k));// output 7
}
}
算法题目: 动态规划 之 最短编辑距离,布布扣,bubuko.com
原文：http://my.oschina.net/u/869174/blog/294696