ACM金牌大神侯卫东老师的四步动规解题秘籍!请收下

Wesley13
• 阅读 881

近年来,国内外科技公司的算法面试中,动态规划几乎成了必考题型。

动规题目类型众多,又没有固定的解题模板,初学者往往摸不着头脑,有时还会混淆动规和递归,所以动态规划又被称为“新人杀手”。

不过动态规划的难,更多是因为初学者不知道怎么入门。学会正确的思考模式和解题流程,掌握动态规划其实并不难。

九章侯卫东老师针对所有动态规划题型,总结了一套4步解题法

ACM金牌大神侯卫东老师的四步动规解题秘籍!请收下

作为清华学霸,全国算法竞赛金牌,ACM全球总决赛选手,FLAG资深面试官,侯卫东老师凭借丰富的刷题和面试经验,用“3枚硬币”深入浅出地讲解动态规划,具体怎么样?通过下面的视频来感受下吧。

更多类型动规题解扫描下方二维码👇👇

ACM金牌大神侯卫东老师的四步动规解题秘籍!请收下

视频中的题目如下:

你有三种硬币,分别面值2元,5元和7元,每种硬币都有足够多。买一本书需要27元。如何用最少的硬币组合正好付清,不需要对方找钱?

关键词“用最少的硬币组合”——求最值问题,可以用动态规划来解决。

1

第一步:确定状态

状态在动态规划中的作用属于定海神针。解动态规划时需要开一个数组,这里的“状态”就是指数组的每个元素f[i]或f[i][j]代表什么。

确定状态需要两个意识: 最后一步和子问题

1.最后一步

这道题中,我们不知道最优策略是什么,但最优策略肯定是K枚硬币a1,a2……aK面值加起来是27。

这里的“最后一步”就是存在最后一枚硬币aK。

除去aK,前面的硬币面值和为27-aK。

ACM金牌大神侯卫东老师的四步动规解题秘籍!请收下

2.子问题

现在问题变成了:最少用多少枚硬币可以拼出27-aK。也就是将原问题(27)转化成了一个子问题,而且规模更小(27-aK)。

这种与原问题内核一致,但是规模更小的问题,就叫子问题。

为了简化定义,我们设状态f(X)=最少用多少枚硬币拼出X。所以问题就从求f(X)变成求f(X-aK)

我们目前还不知道最后的硬币aK面额多少,但它的面额一定只可能是2/5/7之一。

如果aK是2,f(27)应该是f(27-2) + 1 (加上最后这一枚面值2的硬币)

如果aK是5,f(27)应该是f(27-5) + 1 (加上最后这一枚面值5的硬币)

如果aK是7,f(27)应该是f(27-7) + 1 (加上最后这一枚面值7的硬币)

除此以外,没有其他的可能了。

因为要求最少的硬币数,所以问题的解就可以这样表示:

f(27) = min{f(27-2)+1, f(27-5)+1, f(27-7)+1}

2

第二步:转移方程

设状态f[X]=最少用多少枚硬币拼出X

对于任意X,f[X] = min{f[X-2]+1, f[X-5]+1, f[X-7]+1}

ACM金牌大神侯卫东老师的四步动规解题秘籍!请收下

实际面试中,如果正确列出转移方程,问题基本就解决一半了。

很多同学基本也可以做到写出状态转移方程,但真正写程序的时候往往会出现很多错误或问题。

这就涉及到在代码前的两个重要步骤,就是我们4步解题法的第三步和第四步。

3

第三步:初始条件和边界情况

f[X] = min{f[X-2]+1, f[X-5]+1, f[X-7]+1}的边界情况是X-2, X-5或者X-7不能小于0(硬币面值为正)

故对边界情况设定如下:

如果硬币面值不能组合出Y,就定义f[Y]=正无穷

例如f[-1]=f[-2]=…=正无穷;

f[1] =min{f[-1]+1, f[-4]+1,f[-6]+1}=正无穷,表示拼不出1

特殊情况:本题的F[0]对应的情况为F[-2]、F[-5]、F[-7],按照上文的边界情况设定结果是正无穷。

但是实际上F[0]的结果是存在的(即使用0个硬币的情况下),F[0]=0。

这种用转移方程无法计算,但是又实际存在的情况,就必须通过手动定义。

所以这里定义初始条件为:F[0]=0.

而从0之后的数值是没矛盾的,比如F[1]= F[1-2]+1= F[-1]+1=正无穷(正无穷加任何数结果还是正无穷);F[2]= F[2-2]+1= F[0]+1=1……

4

第四步,确定计算顺序

那么开始计算时,是从F[1]、F[2]开始?还是从F[27]、F[26]开始呢?

判断计算顺序正确与否的原则是:

当我们要计算F[X](等式左边,如F[10])的时候,等式右边(f[X-2], f[X-5], f[X-7]等)都是已经得到结果的状态,这个计算顺序就是OK的。

实际就是从小到大的计算方式 (偶有例外的情况我们后边再讲)。

例如我们算到F[12]的时候,发现F[11]、F[10]、F[9]都已经算过了,这种算法就是对的;

而开始算F[27]的时候,发现F[26]还没有算,这样的顺序就是错的。

很显然这样的情况下写一个FOR循环就够了。

回到这道题,采用动态规划的算法,每一步只尝试三种硬币,一共进行了27步。算法时间复杂度(即需要进行的步数)为27*3。

5

最后总结

动态规划4步解题法

  • 确定状态

  • 研究最优策略的最后一步

  • 转化为子问题

  • 转移方程

  • 根据子问题定义直接得到

  • 初始条件和边界情况

  • 细心,考虑周全

  • 计算顺序

  • 利用之前的计算结果

按照以上4步套路,基本上可以解决绝大多数类型的动态规划题。

除了最值型动态规划,想要了解4步法在更多类型动态规划中的运用,可以来听侯卫东老师的《 动态规划专题班 》。

动态规划专题班 免费分享课

ACM金牌大神侯卫东老师的四步动规解题秘籍!请收下

**报名免费试听
**

长按扫码,点击免费试听即可

ACM金牌大神侯卫东老师的四步动规解题秘籍!请收下

或点击下方“阅读原文”

本文分享自微信公众号 - 九章算法(ninechapter)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Jacquelyn38 Jacquelyn38
2年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Kubrnete Kubrnete
3年前
基于01背包问题的动态规划算法
目录初步认识动态规划(初步认识动态规划)与动态规划有关的理论知识:(与动态规划有关的理论知识:)动态规划中的最优决策表(基于填表的动态规划算法)最终版动态规划(最终版动态规划)总结(总结:)初步认识动态规划动态规划算法是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推
Kubrnete Kubrnete
3年前
动态规划之马拉车算法
问题描述:给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。如"abc"有三个回文子串‘a','b','c'.示例1:输入:"abc"输出:3解释:三个回文子串:"a","b","c"示例2:输入:"aaa"输出
Stella981 Stella981
2年前
Android So动态加载 优雅实现与原理分析
背景:漫品Android客户端集成适配转换功能(基于目标识别(So库35M)和人脸识别库(5M)),导致apk体积50M左右,为优化客户端体验,决定实现So文件动态加载.!(https://oscimg.oschina.net/oscnet/00d1ff90e4b34869664fef59e3ec3fdd20b.png)点击上方“蓝字”关注我
Wesley13 Wesley13
2年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Stella981 Stella981
2年前
A Mini Locomotive(动态规划 01)
 /\ 题意:选出3个连续的数的个数 为K的区间,使他们的和最大分析: dp\j\\i\max(dp\jk\\i1\value\j\,dp\j1\\i\);dp\j\\i\:从j个数种选出i个连续区间 数值的最大和value\j\:第j个区间内的数的和和背包有点像,但要活用\
Wesley13 Wesley13
2年前
01背包问题(动态规划求解)
这两天c的习题开始不考察c了,开始考察动态规划问题,唉,没学过动态规划算法来编这题目真是一把辛酸泪,下面给出题目(题目来源:郭玮老师的mooc)2:CharmBracelet查看提交统计提问总时间限制:1000ms内存限制:65536kB描述Bessiehasgonetothemall’s
菜园前端 菜园前端
8个月前
什么是动态规划?
原文链接:什么是动态规划?动态规划也是算法设计的一种方法/思想。它将一个问题分解为相互重叠的子问题,通过反复求解子问题,来解决原来的问题。基础案例场景一斐波那契数列当前数等于前面两个数的和。定义子问题:f(n)f(n1)f(n2)
Python进阶者 Python进阶者
2个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这