重叠子问题,对每个子问题只计算一次,然后将其计算的结果保存到一个表格中,每一次需要上一个子问题解时,进行调用,只要o(1)时间复杂度,准确的说,动态规划是利用空间去换取时间的算法.
判断是否可以利用动态规划求解,第一个是判断是否存在重叠子问题。
爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
分析:
假定n=10,首先考虑最后一步的情况,要么从第九级台阶再走一级到第十级,要么从第八级台阶走两级到第十级,因而,要想到达第十级台阶,最后一步一定是从第八级或者第九级台阶开始.也就是说已知从地面到第八级台阶一共有X种走法,从地面到第九级台阶一共有Y种走法,那么从地面到第十级台阶一共有X+Y种走法.
即F(10)=F(9)+F(8)
分析到这里,动态规划的三要素出来了.
边界:F(1)=1,F(2)=2
最优子结构:F(10)的最优子结构即F(9)和F(8)
状态转移函数:F(n)=F(n-1)+F(n-2)
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
if n<=2:
return n
a=1#边界
b=2#边界
temp=0
for i in range(3,n+1):
temp=a+b#状态转移
a=b#最优子结构
b=temp#最优子结构
return temp
编辑距离是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。通常来说，编辑距离越小，两个文本的相似性越大。这里的编辑操作主要包括三种：
插入：将一个字符插入某个字符串；
删除：将字符串中的某个字符删除；
替换：将字符串中的某个字符替换为另外一个字符。
那么，如何用Python计算编辑距离呢？我们可以从较为简单的情况进行分析。
当两个字符串都为空串，那么编辑距离为0；
当其中一个字符串为空串时，那么编辑距离为另一个非空字符串的长度；
当两个字符串均为非空时(长度分别为 i 和 j )，取以下三种情况最小值即可：
1、长度分别为 i-1 和 j 的字符串的编辑距离已知，那么加1即可；
2、长度分别为 i 和 j-1 的字符串的编辑距离已知，那么加1即可；
3、长度分别为 i-1 和 j-1 的字符串的编辑距离已知，此时考虑两种情况，若第i个字符和第j个字符不同，那么加1即可；如果相同，那么不需要加1。
很明显，上述算法的思想即为 动态规划 。
求长度为m和n的字符串的编辑距离，首先定义函数——edit(i, j)，它表示第一个长度为i的字符串与第二个长度为j的字符串之间的编辑距离。动态规划表达式可以写为：
if i == 0 且 j == 0，edit(i, j) = 0
if （i == 0 且 j >0 ）或者 （i >0 且j == 0），edit(i, j) = i + j
if i ≥ 1 且 j ≥ 1 ，edit(i, j) == min{ edit(i-1, j) + 1, edit(i, j-1) + 1, edit(i-1, j-1) + d(i, j) }，当第一个字符串的第i个字符不等于第二个字符串的第j个字符时，d(i, j) = 1；否则，d(i, j) = 0。
def edit_distance(word1, word2):
len1 = len(word1)
len2 = len(word2)
dp = np.zeros((len1 + 1,len2 + 1))
for i in range(len1 + 1):
dp[i][0] = i
for j in range(len2 + 1):
dp[0][j] = j
for i in range(1, len1 + 1):
for j in range(1, len2 + 1):
delta = 0 if word1[i-1] == word2[j-1] else 1
dp[i][j] = min(dp[i - 1][j - 1] + delta, min(dp[i-1][j] + 1, dp[i][j - 1] + 1))
return dp[len1][len2]
edit_distance('牛奶','华西奶')
结果：2
分析题目，其实就是尽量保留原来的字母。
首先按照字母出现的顺序找出要保留的字母，然后，其他的从源单词删除，然后把插入目标中的其他字母。
算法是个人推理，没有证明100%正确，做个参考把（python3）：
def get_copy_del_chars(src, des):start = 0
result = []
for char in src:
pos = des[start:].find(char)
if pos >= 0:
result.append(('c', char))
start = start + pos + 1
else:
result.append(('d', char))
return result
def word2word(src, des):
copy_del_chars = get_copy_del_chars(src, des)
result = []
idx = 0
for action, char in copy_del_chars:
if action == 'd':
result.append((action, char))
continue
if des[idx] == char:
result.append((action, char))
idx += 1
continue
while True:
result.append(('i', des[idx]))
idx += 1
if des[idx] == char:
result.append((action, char))
idx += 1
break
return result
def calc_score(operates):
score_map = {'i': 20, 'c': 5, 'd': 20}
return sum(score_map[op[0]] for op in operates)
if __name__ == '__main__':
operates = word2word('algorithm', 'alligator')
print(calc_score(operates))
进入python-Levenshtein 源码目录下有setup.py ，安装用 python setup.py install使用python-Levenshtein模块
import Levenshtein
算法说明
1). Levenshtein.hamming(str1, str2)
计算汉明距离。要求str1和str2必须长度一致。是描述两个等长字串之间对应 位置上不同字符的个数。
2). Levenshtein.distance(str1, str2)
计算编辑距离（也称为 Levenshtein距离）。是描述由一个字串转化成另一个字串最少的操作次数，在其中的操作包括插入、删除、替换。
算法实现参考动态规划整理。
3). Levenshtein.ratio(str1, str2)
计算莱文斯坦比。计算公式r = (sum - ldist) / sum, 其中sum是指str1 和 str2 字串的长度总和，ldist是 类编辑距离
注意：这里的类编辑距离不是2中所说的编辑距离，2中三种操作中每个操作+1，而在此处，删除、插入依然+1，但是替换+2
这样设计的目的：ratio('a', 'c')，sum=2, 按2中计算为（2-1）/2 = 0.5,’a','c'没有重合，显然不合算，但是替换操作+2，就可以解决这个问题。
4). Levenshtein.jaro(s1 , s2 )
