初级算法实践之动态规划

栏目: 编程工具 · 发布时间: 4年前

内容简介:动态规划,很多人望而生畏的名词之一。其实,动态规划只是一种思想。即将现有问题拆分为若干子问题,分别求之,最后合并子问题的结果求出当前问题的答案。

一、背景

动态规划,很多人望而生畏的名词之一。

其实,动态规划只是一种思想。

即将现有问题拆分为若干子问题,分别求之,最后合并子问题的结果求出当前问题的答案。

在拆分子问题的时候,可能涉及到子问题的重复运算。

所以需要使用对子问题的计算结果进行保存,下次需要的时候直接返回结果即可。

这里涉及到两个关键点。

1.可以拆分为子问题,并由子问题的答案计算出当前问题的答案。

2.子问题的结果可以保存起来的。

有了这两个关键步骤,我们就可以解决大部分动态规划题了。

比如下面有四道动态规划题,你应该都可以学会。

二、爬楼梯

题意:有一个 n 层的台阶,现在你要从底部爬到顶部。

你每次可以爬一层,也可以爬两层。

问你有多少种不同的路径从底部爬到顶部。

思路:我们可以只看第 n 个台阶。

则第 n 个台阶可能由两个台阶到达,一个是第 n-1 个台阶,一个是 n-2 个台阶。

所以从底部到达第 n 个台阶的路径个数可以拆分为两类。

一类是从底部先到达第 n-1 个台阶,然后再到达第 n 个台阶。

另一类是从底部先到达第 n-2 个台阶,然后直接到达第 n 个台阶。

从底部到达第 n 个台阶我们用 f(n) 表示。

则上面的子问题可以由公式 f(n) = f(n-1) + f(n-2) 表示。

而对于子问题的结果,则可以储存在一个一维数组里面。

自此,这道题就可以完美解决了。

初级算法实践之动态规划

三、买卖股票的最佳时机

题意:给出一支股票连续若干天的价格。

假设我们只能买卖一次,怎么才能收益最大化呢?

思路:假设是 n 天,则问题可以拆分为两部分:第 n 天卖出,或者前 n-1 天操作。

定义 f(n) 为前 n 天买卖一次的最优解。

定义 F(n) 为第 n 天卖出一次的最优解。

则可以写出下面两个公式:

f(n) = max(f(n-1), F(n))
F(n) = A[n] - min(n-1)

min(n-1) 为前 n-1 天股票的最低价。

由此,这道题我们就做出来了。

当然,拆分问题的时候,也可以拆分为: f(n) = max(F(n), F(n-1), ..., F(1))
不过此时, f(n) 这个定义就没意义了,因为子问题里没有再出现这个定义。

初级算法实践之动态规划

四、最大子序和

题意:给一个数组,找一个连续子数组,使得这个子数组的和最大,返回最大和。

思路:最经典的动态规划题。

按照上面一题的拆分思路,我们同样可以拆分为两个状态。

定义 f(n) 为前 n 个数字的最优值。

定义 F(n) 为第 n 个数字为连续数组最后一个数字时,最优值。

f(n) 可以分两种情况,一种是最后一天属于连续数字,一种是不属于,结果去最优值。

f(n) = max(f(n-1), F(n))

F(n) 也可以分两种情况,一种是自己单独组成连续数字,一种是和前面的连在一起,结果也是取最大值。

F(n) = max(A[n], A[n] + F(n-1))

看到这里,是不是发现这道题和上一题几乎一抹一样?

f(n) 可以拆分为假设每一天为连续数字的最后一个的子问题。

f(n) = max(F(n), F(n-1), ..., F(1))

这里和上一题不同的地方在于,这道题我们知道一些必胜策略。

比如假设 F(n-1) < 0 ,那么 F(n) 的决策肯定是 A[n] ,而不是 A[n]+F(n-1)

因为 A[n] 肯定大于 A[n]+F(n-1) 的。

由于这道题比较简单,这个必胜决策的效果不容易看出来,但是大家需要知道有这么一个概念。

在搜索中,这种情况可以用于剪枝,用来过滤明显不是最优解的子问题。

初级算法实践之动态规划

五、打家劫舍

题意:给一个数组,我们可以挑选若干位置的值,使得和最大。

条件:挑选的位置不能连续。

思路:定义 f(n) 为答案。

则可以拆分为两个问题:第 n 个是否挑选。

挑选,则只能挑选前 n-2 个元素;

不挑选,则可以从 n-1 个元素开始挑选。

公式为 f(n) = max(f(n-1), A[n] + f(n-2))

前面的几道题都是使用递推实现的,这个就使用递归实现吧。

初级算法实践之动态规划

六、最后

看了这四道题有没有发现动态规划还是很简单的呢?

如果给的题意就可以直接拆分子问题,则大部分都可以做出来。

如果题意不能拆分子问题,或者拆分的子问题无解,则需要转换一下题意,构造出一个可以拆分出子问题并求解的问题来。

当然,这里也是最难得。

随着大家的刻意练习,分析问题的能力会越来越强,那时候,大家就能够自己构造出可以求解的子问题了。

-EOF-


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

快速转行做产品经理

快速转行做产品经理

李三科 / 华中科技大学出版社 / 2018-6-1 / 39.90

互联网已经进入以产品为中心的时代,不懂技术一样做高薪产品经理。本书将满足你转行、就业、加薪的愿望。 . 作者李三科,互联网资深产品经理。2011年离开传统销售行业进入互联网行业工作,从对产品经理的工作一无所知,到成长为一名年薪几十万的资深产品经理,他对产品经理职业有着深刻的理解,也积累了丰富的学习、工作经验。本书以作者亲身经历为线索,讲解学习产品经理相关知识和工作方法的经验,同时介绍求......一起来看看 《快速转行做产品经理》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具