python动态规划及编辑距离计算实例

动态规划的三要素:最优子结构,边界和状态转移函数,最优子结构是指每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到(子问题的最优解能够决定这个问题的最优解),边界指的是问题最小子集的解(初始范围),状态转移函数是指从一个阶段向另一个阶段过度的具体形式,描述的是两个相邻子问题之间的关系(递推式)

成都创新互联公司主营河北网站建设的网络公司,主营网站建设方案,成都app软件开发公司,河北h5小程序开发搭建,河北网站营销推广欢迎河北等地区企业咨询

重叠子问题,对每个子问题只计算一次,然后将其计算的结果保存到一个表格中,每一次需要上一个子问题解时,进行调用,只要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

爬楼梯问题【多解法】

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注：n 是一个正整数。

输入： 2

输出： 2

解释： 有两种方法可以爬到楼顶。

输入： 3

输出： 3

解释： 有三种方法可以爬到楼顶。

在暴力法中，我们将会把所有可能爬的阶数进行组合，也就是 1 和 2 。而在每一步中我们都会继续调用 climbStairs，climbStairs 这个函数模拟爬 1 阶和 2 阶的情形，并返回两个函数的返回值之和。

climbStairs(i,n) = climbStairs(i + 1, n) + climbStairs(i + 2, n)

其中 i 定义了当前阶数，而 n 定义了目标阶数。

在 n=5 时的递归树将是这样的：

在上一种方法中，我们计算每一步的结果时出现了冗余。另一种思路是，我们可以把每一步的结果存储在 memory 数组之中，每当函数再次被调用，我们就直接从 memory 数组返回结果。

在 memory 数组的帮助下，我们得到了一个修复的递归树，其大小减少到 n 。

不难发现，这个问题可以被分解为一些包含最优子结构的子问题，即它的最优解可以从其子问题的最优解来有效地构建，我们可以使用动态规划来解决这一问题。

第 ii 阶可以由以下两种方法得到：

在第 (i-1) 阶后向上爬 1 阶。

在第 (i-2) 阶后向上爬 2 阶。

所以到达第 i 阶的方法总数就是到第 (i−1) 阶和第 (i−2) 阶的方法数之和。

令 dp[i] 表示能到达第 i 阶的方法总数：

dp[i]=dp[i-1]+dp[i-2]

在上述方法中，我们使用 dp 数组，其中 dp[i]=dp[i-1]+dp[i-2]。可以很容易通过分析得出 dp[i] 其实就是第 i 个斐波那契数。

Fib(n)=Fib(n-1)+Fib(n-2)

现在我们必须找出以 1 和 2 作为第一项和第二项的斐波那契数列中的第 n 个数，也就是说 Fib(1)=1 且 Fib(2)=2。

方法 5: Binets 方法

算法

这里有一种有趣的解法，它使用矩阵乘法来得到第 nn 个斐波那契数。矩阵形式如下：

令

按照此方法，第 nn 个斐波那契数可以由 Q n-1 [0,0] 给出。

让我们试着证明一下。

我们可以使用数学归纳法来证明这一方法。易知，该矩阵给出了第 3 项（基本情况）的正确结果。由于

这证明基本情况是成立的。

假设此方法适用于查找第 nn 个斐波那契数，即 F n =Q n-1 [0,0]，那么：

现在，我们需要证明在上述两个条件为真的情况下，该方法可以有效找出第 (n+1) 个斐波那契数，即，F n+1 =Q n [0,0]。

证明：

从而， F n+1 =Q n [0,0]。得证。

我们需要为我们的问题做的唯一改动就是将斐波那契数列的初始项修改为 2 和 1 来代替原来的 1 和 0 。或者，另一种方法是使用相同的初始矩阵 Q 并使用 result = Q n [0,0] 得出最后结果。发生这种情况的原因是我们必须使用原斐波那契数列的第 2 项和第 3 项作为初始项。

我们可以使用这一公式来找出第 n 个斐波那契数：

对于给定的问题，斐波那契序列将会被定义为 F 0 = 1，F 1 = 1，F 2 = 2，F n+2 = F n+1 + F n 。尝试解决这一递归公式的标准方法是设出 F n ，其形式为 F n = a n 。然后，自然有 F n+1 = a n+1 和 F n+2 = a n+2 ，所以方程可以写作 a n+2 = a n+1 + a n 。如果我们对整个方程进行约分，可以得到 a 2 = a + 1 或者写成二次方程形式 a 2 - a- 1= 0。

对二次公式求解，我们得到:

一般解采用以下形式：

n = 0时，有A + B = 1

n = 1时，有

解上述等式，我们得到：

将 AA 和 BB 的这些值带入上述的一般解方程中，可以得到：

小明爬楼梯

共有2082876103种，其实这是一道典型的递归编程题，与其说是数学题，不如说是属于计算机科学的范畴。

设f(n)表示n级台阶的爬法数目，则前几个f值可以穷举得f(1)=1，f(2)=2，f(3)=4。

n=4后，有如下递归关系：f(n)=f(n-1)+f(n-2)+f(n-3)，因为把爬n级台阶的最后一步分类，则f(n-1)代表最后一步是爬1级的所有走法，f(n-2)代表最后一步是爬2级的所有走法，f(n-3)代表最后一步是爬3级的所有走法，因此关系式成立。

用计算机迭代，得36级台阶的爬法数目为f(36)=2082876103种。

Matlab语言程序：

f=zeros(1,36);

f(1)=1; f(2)=2; f(3)=4;

for i=4:36

f(i)=f(i-1)+f(i-2)+f(i-3);

end

f(36)

如果想求解析解，可以考虑特征方程x^3=x^2+x+1的根为X，Y，Z，则数列的通解为

f(n)=A*X^n+B*Y^n+C*Z^n，通过f(1)，f(2)，f(3)的值，可以求出待定系数A，B和C。不过看来是挺麻烦的，因为特征方程的解是一个无理实数，和两个共轭虚数。

Python算法-爬楼梯与递归函数

可以看出来的是，该题可以用斐波那契数列解决。

楼梯一共有n层，每次只能走1层或者2层，而要走到最终的n层。不是从n-1或者就是n-2来的。

F(1) = 1

F(2) = 2

F(n) = F(n-1) + F(n-2) (n=3)

这是递归写法，但是会导致栈溢出。在计算机中，函数的调用是通过栈进行实现的，如果递归调用的次数过多，就会导致栈溢出。

针对这种情况就要使用方法二，改成非递归函数。

将递归进行改写，实现循环就不会导致栈溢出

python 爬楼梯（lintcode）

爬楼梯

原题地址：

假设你正在爬楼梯，需要n步你才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法爬到楼顶部？

比如n=3，1+1+1=1+2=2+1=3，共有3种不同的方法

返回 3

这道题本质上就是一道斐波那契数列的应用

假设一共有10阶楼梯，每步可以爬1步或者2步，那么你爬到10阶一共有两种方法，从8阶爬2步，或从9阶爬1步，那么爬到9阶也是这样，那这就是一共基本的斐波那契数列。

递归算法

ted斐波那契数列：

还有一种快速求幂法：

python爬楼梯求至少多少阶梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。

注意：给定 n 是一个正整数。

示例 1：

输入： 2

输出： 2

解释： 有两种方法可以爬到楼顶。1 阶 + 1 阶 和 2 阶

解题思路：

实现了两种方法，但是第一种超出时间限制(｡ì _ í｡)，因为递归的时候方法实际计算了两次。两种方法都使用了动态规划思想，比如对于爬10阶楼梯，我们最后一步爬上第10阶只会有两种情况，一种是从9阶楼梯爬1个台阶，一种是从8阶台阶爬2两个台阶上来。所以10阶台阶问题可以划分为爬9阶和8阶两个子问题，一直递归划分到只剩2阶(2种方法)和1阶(一种方法)。

超出时间限制的代码：

class Solution:

def climbStairs(self, n: int) - int:

if n=2:

if n==2:

网页名称：python爬楼梯函数 python爬楼梯问题列表法
新闻来源：http://scyanting.com/article/hpjpii.html