导航:首页 > 源码编译 > 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算法中文版相关的资料

热点内容
cad计算机命令 浏览:171
邮箱设置域名服务器错误什么意思 浏览:669
硬盘解压失败受损蓝屏 浏览:654
应用和服务器是什么意思 浏览:485
程序员需要知道的网站 浏览:713
微信支付页面加密码怎么加 浏览:57
网络加密狗问题 浏览:698
cnc曲面编程实例 浏览:170
什么app零粉分发视频有收益 浏览:164
肯尼亚程序员 浏览:640
新科源码 浏览:661
如何判断服务器有没有带宽 浏览:44
天正建筑批量删除命令 浏览:96
cad最下面的一排命令都什么意思 浏览:456
pythonimportcpp 浏览:852
W10的系统怎么给U盘加密 浏览:372
华为手机代码编程教学入门 浏览:764
和彩云没会员怎样解压 浏览:636
androidimageview保存 浏览:389
新买店铺什么服务器 浏览:886