今天面试，遇到一个面试题，没想通，请各位帮我解答一下。
Write a Windows form application that returns the difference of two given files using Levenshtein distance (edit distance).A commonly-used bottom-up dynamic programming algorithm for computing the Levenshtein distance involves the use of an (n + 1) × (m + 1) matrix, where n and m are the lengths of the two strings. Here is pseudocode for a function LevenshteinDistance that takes two strings, s of length m, and t of length n, and computes the Levenshtein distance between them:
int LevenshteinDistance(char s[1..m], char t[1..n])
// d is a table with m+1 rows and n+1 columns
declare int d[0..m, 0..n]
for i from 0 to m
d[i, 0] := i
for j from 1 to n
d[0, j] := j
for i from 1 to m
for j from 1 to n
if s[i] = t[j] then cost := 0
else cost := 1
d[i, j] := minimum(
d[i-1, j] + 1, // deletion
d[i, j-1] + 1, // insertion
d[i-1, j-1] + cost // substitution
)
return d[m, n]
Two examples of the resulting matrix (the minimum steps to be taken are highlighted):
k i t t e n
0 1 2 3 4 5 6
s 1 1 2 3 4 5 6
i 2 2 1 2 3 4 5
t 3 3 2 1 2 3 4
t 4 4 3 2 1 2 3
i 5 5 4 3 2 2 3
n 6 6 5 4 3 3 2
g 7 7 6 5 4 4 3
S a t u r d a y
0 1 2 3 4 5 6 7 8
S 1 0 1 2 3 4 5 6 7
u 2 1 1 2 2 3 4 5 6
n 3 2 2 2 3 3 4 5 6
d 4 3 3 3 3 4 3 4 5
a 5 4 3 4 4 4 4 3 4
y 6 5 4 4 5 5 5 4 3
The invariant maintained throughout the algorithm is that we can transform the initial segment s[1..i] into t[1..j] using a minimum of d[i,j] operations. At the end, the bottom-right element of the array contains the answer.
--------------------编程问答-------------------- 看不懂英文，先翻译下 --------------------编程问答-------------------- 呵呵，不像面试题， 是LZ的作业吧
不好好学习，还要骗人，该打 --------------------编程问答--------------------
那么就当是帮一下困惑的学生，怎么样？ --------------------编程问答-------------------- 不清楚你“没想通什么”。
建议你搜索"动态规划（DP，dynamic programming）"，它是解决问题的算法。
如果不理解什么是"编辑距离（Levenshtein distance）"，也可以搜索。
网上介绍编辑距离和动态规划的文章非常多，解释也很清楚。 --------------------编程问答--------------------
不怎么样，冲你这问问题的爷们范儿就没觉得你是真诚的想解惑。 --------------------编程问答--------------------
请写一个Windows表单（就是带有若干控件的窗口）程序，根据Levenshtein距离（编辑距离），计算出两个文件的差异。
计算Levenshtein距离通常采用的自底向上动态编程算法，需要用到一个(n + 1) × (m + 1) 的矩阵，n和m分别是两个字符串的长度。这里有一个函数LevenshteinDistance的伪代码，传入参数是：字符串s及其长度m、字符串t及其长度n。该函数计算两者的Levenshtein距离。
这个算法中，有一点自始至终保持不变：我们最少只需d[i,j]步操作即可以把（任意）初始的字符段s[1..i] 变换为t[1..j]。当算法执行结束后，数组右下方的元素就是最终结果。 --------------------编程问答--------------------
可能你听的语气味道不对吧。 --------------------编程问答--------------------
呵呵呵呵呵呵 --------------------编程问答--------------------
＝＝＝＝＝＝＝＝＝＝＝
呵呵呵呵呵呵 --------------------编程问答-------------------- LD算法 ，百度很多代码 --------------------编程问答--------------------
class CompareString--------------------编程问答--------------------
{
public int Compare(string S, string D)
{
if (string.IsNullOrEmpty(S) || string.IsNullOrEmpty(D))
throw new Exception("String should not be empty.");
int[,] array = new int[S.Length + 1, D.Length + 1];
for (int i = 0; i <= S.Length; i++)
array[i, 0] = i;
for (int i = 1; i <= D.Length; i++)
array[0, i] = i;
for (int i = 1; i <= S.Length; i++)
{
for (int j = 1; j <= D.Length; j++)
{
int c = S[i - 1] == D[j - 1] ? 0 : 1;
int n1 = array[i - 1, j] + 1;
int n2 = array[i - 1, j - 1] + c;
int n3 = array[i, j - 1] + 1;
int v = n1 < n2 ? n1 : n2;
array[i, j] = v < n3 ? v : n3;
}
}
return array[S.Length, D.Length];
}
}
请问楼主的爷们范儿从哪里可以分析出？ --------------------编程问答--------------------
课后习题当诈称面试题，我只能呵呵呵呵呵了 --------------------编程问答--------------------
楼主把别人都当傻逼看，也许这样的伎俩真的可以骗过楼主自己。 --------------------编程问答-------------------- 你搜索"动态规划（DP，dynamic programming）"，它是解决问题的算法。
如果不理解什么是"编辑距离（Levenshtein distance）"，也可以搜索。 --------------------编程问答-------------------- 感谢版主，我也搜索到答案了。
至于是课后习题还是面试题，我真不想在此纠结。
1、我可以拿出别人出面试题的照片
2、即使是我拿的课后习题，我拿到这儿来问，有什么问题吗？
3、我面试的，是实验室的工作内容，而我做asp.net时间长了，对算法确实不行了。而他们希望我转做别的语言，所以对算法有要求。
补充：.NET技术 , C#
