#!/usr/bin/env python
#coding=utf-8
def word_distance(m,n):
"""compute the least steps number to convert m to n by insert , delete , replace .
动态规划算法,计算单词距离
>>> print word_distance("abc","abec")
1
>>> print word_distance("ababec","abc")
3
"""
len_1=lambda x:len(x)+1
c=[[i] for i in range(0,len_1(m)) ]
c[0]=[j for j in range(0,len_1(n))]
for i in range(0,len(m)):
# print i,' ',
for j in range(0,len(n)):
c[i+1].append(
min(
c[i][j+1]+1,#插入n[j]
c[i+1][j]+1,#删除m[j]
c[i][j] + (0 if m[i]==n[j] else 1 )#改
)
)
# print c[i+1][j+1],m[i],n[j],' ',
# print ''
return c[-1][-1]
import doctest
doctest.testmod()
raw_input("Success!")
分享到:
- 2007-11-04 09:40
- 浏览 2822
- 评论(0)
- 论坛回复 / 浏览 (0 / 2862)
- 查看更多
相关推荐
本文实例讲述了Python基于动态规划算法计算单词距离。分享给大家供大家参考。具体如下: #!/usr/bin/env python #coding=utf-8 def word_distance(m,n): compute the least steps number to convert m to n by ...
几道动态规划的经典算法 非常经典 值得分享
在计算机算法设计方法中,动态规划技术是比较基本,但又比较抽象,难于理解的一种。它建立在最优原则的基础上,动态规划 ( dynamic programming )算法是解决多阶段决策过程最优化问题的一种常用方法,难度比较大,...
动态规划算法与贪心算法动态规划算法与贪心算法动态规划算法与贪心算法动态规划算法与贪心算法动态规划算法与贪心算法动态规划算法与贪心算法动态规划算法与贪心算法
动态规划 动态规划 动态规划 动态规划 动态规划 动态规划
动态规划算法简介 动态规划算法很详细 有典型例子 适合初学者
1.掌握动态规划算法的基本思想,包括最优子结构性质和基于表格的最优值计算方法。 2.熟练掌握分阶段的和递推的最优子结构分析方法。 3.学会利用动态规划算法解决实际问题。 题目一:数塔问题 给定一个数塔,其...
1、 掌握动态规划算法的基本步骤:找出最优解的性质,并刻画其结构特征;递归地定义最优值;以自底向上的方式计算出最优值;根据计算最优值时得到的信息,构造最优解。 求X和Y的最长公共子序列长度以及最长公共子...
《动态规划算法实验》实验报告
【达摩老生出品,必属...资源名:matlab实现动态规划算法 程序源码.zip 资源类型:程序源代码 源码说明: 基于matlab实现动态规划的程序,包含完整源码和注释,非常适合借鉴学习 适合人群:新手及有一定经验的开发人员
利用动态规划算法解决图形图像处理问题,用Java编写,代码经过调试健壮性良好
动态规划算法将原问题...为了避免重复计算,动态规划算法采用了填表来保存子问题解的方法。 在算法中用表格来保存已经求解的子问题的解,无论它是否会被用到。当以后遇到该子问题时即可查表取出其解,避免了重复计算。
动态规划算法实现投资问题,老师给的比较实用的,呵呵,希望大家多多采纳
用动态规划算法求解TSP,数据为Solomon数据集的c101文件读取,可视化路径图,用图展示每次迭代的最优值、最差值和平均值,并与Gurobi求解结果比较各计算时间下的目标值。动态规划算法求解TSP 用动态规划算法求解TSP...
动态规划算法课件PPT,读者可以参考,非常不错的,清华老师的
动态规划算法(下).ppt动态规划算法(下).ppt动态规划算法(下).ppt
动态规划算法ppt讲义
动态规划算法 数据结构 算法导论 编程思想 程序员指定用书
c/c++语言的动态规划算法动态规划动态规划动态规划动态规划