利用动态规划算法，实现最短编辑距离的计算。
复制代码 代码如下:
#encoding: utf-8
#author: xu jin
#date: Nov 12, 2012
#EditDistance
#to find the minimum cost by using EditDistance algorithm
#example output:
# "Please input a string: "
# exponential
# "Please input the other string: "
# polynomial
# "The expected cost is 6"
# The result is :
# ["e", "x", "p", "o", "n", "e", "n", "-", "t", "i", "a", "l"]
# ["-", "-", "p", "o", "l", "y", "n", "o", "m", "i", "a", "l"]
p "Please input a string: "
x = gets.chop.chars.map{|c| c}
p "Please input the other string: "
y = gets.chop.chars.map{|c| c}
x.unshift(" ")
y.unshift(" ")
e = Array.new(x.size){Array.new(y.size)}
flag = Array.new(x.size){Array.new(y.size)}
DEL, INS, CHA, FIT = (1..4).to_a #deleat, insert, change, and fit
def edit_distance(x, y, e, flag)
(0..x.length - 1).each{|i| e[i][0] = i}
(0..y.length - 1).each{|j| e[0][j] = j}
diff = Array.new(x.size){Array.new(y.size)}
for i in(1..x.length - 1) do
for j in(1..y.length - 1) do
diff[i][j] = (x[i] == y[j])"The expected edit distance is #{e[x.length - 1][y.length - 1]}"
solution_structure(x, y, flag, x.length - 1, y.length - 1, out_x, out_y)
puts "The result is : \n #{out_x}\n #{out_y}"