导航:首页 > 源码编译 > python算法中文版

python算法中文版

发布时间:2022-08-25 07:28:53

1. 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算法中文版相关的资料

热点内容
编程知识大全女孩 浏览:62
aut命令 浏览:429
什么儿童编程好 浏览:646
产品经理的第一本书pdf 浏览:430
app源在哪里 浏览:25
excel中命令按钮 浏览:91
记录仪安卓起动优化是怎么回事 浏览:657
java1970毫秒 浏览:443
程序员发家前景 浏览:750
linux服务器类型 浏览:408
php免杀大马在线 浏览:35
程序员珠海6000元工资 浏览:209
中国出名残疾程序员 浏览:829
数控机床编程例子带说明 浏览:447
我是女王pdf 浏览:651
python编程怎么接私单 浏览:789
linux线程限制 浏览:761
课程app怎么设计 浏览:112
javaxml序列化反序列化 浏览:859
在线文件夹名字 浏览:166