Python之动态规划算法

Python019

Python之动态规划算法,第1张

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

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

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

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

上述代码，随着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运行通过。

找一个 __init__.py 文件, 导入这个库文件,然后写一个新的方法,将方法赋值给这个模块

比如第三方库是这样的 third.py -> many.py

那么在项目的一个 __init__.py 文件(可以是配置文件)写入

可以。

Python源代码：

from random import randint from time import sleepimport coloramafrom colorama import Fore, Back, Stylecolorama.init()rnd2 = randint(1,60)def gentree():for x in range(1,30,2):rnd1 = randint(1,rnd2)if x == 1:ch = "$"elif rnd1 % 4 == 0:ch =  "o"elif rnd1 % 3 == 0:ch = "j"elif rnd1 % 5 == 0:ch = "o"elif rnd1 % 7 == 0:ch = "j"else:ch ="*"if ch == "$":print(Fore.RED +"{:^33}".format(ch * x))elif ch == "o":print(Fore.RED +"{:^33}".format(ch * x))elif ch == "j":print(Fore.YELLOW +"{:^33}".format(ch * x))else:print(Fore.GREEN +"{:^33}".format(ch * x))print("{:^33}".format('|||'))print("{:^33}".format('|||')) print("{:^33}".format('         Merry_christmas         '))sleep(.24)gentree()