python动态规划（Python动态规划经典数塔问题）

本篇文章给大家谈谈python动态规划，以及Python动态规划经典数塔问题对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、Python编程题求助
• 2、Python之动态规划算法
• 3、python动态规划及编辑距离计算实例
• 4、求Python代码编动态规划贝尔曼函数

Python编程题求助

该答案为组合数学中著名的卡特兰数，其通式为C(2n,n)-C(2n,n-1)

这里采用递推关系求解，即老早拍动态规划的方法

设n对父子有d[n]种出场策略，注意初值d[0]=1

因为每个孩子前面必有一个父亲与之对应

对于i对父子，遍历第j个孩子，该孩子前面有j-1个孩子，对应d[j-1]种出场侍羡策略

后面有i-j个孩子，对应d[i-j]种出场策略，则睁弊d[i]+=d[j-1]*d[i-j]，最终d[n]即为所求

python代码如下：

n = int(input())

d = [0] * (n+1)

d[0] = 1

for i in range(n+1):

  for j in range(i+1):

      d[i] += d[j-1] * d[i-j]

print(d[n])

运行结果如下：

望采纳~

Python之动态规划算法

动态规划算法中是将复杂问题递归分解为子问题，通过解决这皮拆些子问题来解决复杂问题。与递归算法相比，动态编程减少了堆栈的使用，避免了重复的计算，效率得到显著提升。

先来看一个简单的例子，斐波那契数列.

斐波那契数列的定义如下。

斐波那契数列可以很容易地用递归算法实现：

上述代码，随燃旁枣着n的增加，计算量呈指数级增长，算法的时间复杂度是 。

采用动态规划算法，通过自下而上的计算数列的值，可以使算法复杂度减小到 ，代码如下。

下面我们再看一个复杂一些的例子。

这是小学奥数常见的硬币问题： 已知有1分，2分，5分三种硬币数量不限，用这些硬币凑成为n分钱，那么一共有多少种组合方法。

我们将硬币的种类用列表 coins 定义；

将问题定义为一个二维数组 dp，dp[amt][j] 是使用 coins 中前 j+1 种硬币( coins[0:j+1] )凑成总价amt的组合数。

例如： coins = [1,2,5]

dp[5][1] 就是使用前两种硬币 [1,2] 凑成总和为5的组合数。

对于所有的 dp[0][j] 来说，凑成总价为0的情况只有一种，就是所有的硬币数量都为0。所以对于在有效范围内任意的j，都有 dp[0][j] 为1。

对于 dp[amt][j] 的计算，也就是使用 coins[0:j+1] 硬币总价amt的组合数，包含两种情况计算：

1.当使用第j个硬币时，有 dp[amt-coins[j]][j] 种情况，即amt减去第j个硬币币值，使用前j+1种硬币的组合数；

2.当不使用第j个硬币时，有 dp[amt][j-1] 种情况，即使用前j种硬币凑成amt的组合数；

所以： dp[amt][j] = dp[amt - coins[j]][j]+dp[amt][j-1]

我们最终得到的结果是：dp[amount][-1]

上述分析省略了一些边界情况。

有了上述的分析，代码实现就比较简单了。

动态规划算法代码简洁，执行效率高。但是与递归算法相比，需要仔细考虑如何分解问题，动态规划代码与递归调用相比，较难理解。

我把递归算法启瞎实现的代码也附在下面。有兴趣的朋友可以比较一下两种算法的时间复杂度有多大差别。

上述代码在Python 3.7运行通过。

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

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

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

[img]

求Python代码编动态规划贝尔曼函数

class Node(object):

    def __init__(self, name):

        self._name = name

        self._value = None

        self._from = None

        self._next = []

    def setValue(self, value):

        self._value = value

    def setNext(self, node):

        self._next.append(node)

    def setFrom(self, node):

        self._from = node

    def getValue(self):

        return self._value

    def getNext(self):

        return self._next

    def getName(self):

        return self._name

    def getFrom(self):

        return self._from

    

class BFtree():

    def __init__(self, dList):

        self._dList = dList

    def bfValue(self, start):

        cur = start

        if cur.getNext() is not None:

            for node in cur.getNext():

         返蔽 凳槐      枣世友path = [cur.getName(),  node.getName()]

                path.sort()

                path = ''.join(path)

                value = cur.getValue() + self._dList[path]

                if node.getValue() is None or value  node.getValue():

                    node.setValue(value)

                    node.setFrom(cur)

                    self.bfValue(node)

    def move(self, start, end):

        print 'From: ', start.getName(), ' to: ', end.getName()

        start.setValue(0)

        self.bfValue(start)

        trace = [end.getName()]

        cur = end

        while cur.getFrom() is not None:

            cur = cur.getFrom()

            trace.append(cur.getName())

        trace = reversed(trace)

        print 'The path is ', ' '.join(trace),' and the value is ', end.getValue()

                

#builidng node

a = Node('A')

b = Node('B')

c = Node('C')

d = Node('D')

e = Node('E')

f = Node('F')

g = Node('G')

h = Node('H')

#build tree

a.setNext(b)

a.setNext(c)

a.setNext(d)

b.setNext(a)

b.setNext(g)

c.setNext(a)

c.setNext(g)

c.setNext(e)

d.setNext(a)

d.setNext(e)

e.setNext(c)

e.setNext(b)

e.setNext(f)

f.setNext(e)

g.setNext(b)

g.setNext(c)

g.setNext(h)

h.setNext(g)

#build distance list

dList = dict();

dList['AB'] = 1

dList['AC'] = 2

dList['AD'] = 3

dList['BG'] = 1

dList['BE'] = 6

dList['CE'] = 2

dList['CG'] = 5

dList['DE'] = 4

dList['EF'] = 3

dList['GH'] = 4

#build BFtree

tree = BFtree(dList)

tree.move(a,h)

tree.move(a,f)

tree.move(a,e)

代码略长....

关于python动态规划和Python动态规划经典数塔问题的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。