有了四步解题法模板,再也不害怕动态规划! | 算法必看系列十六-阿里云开发者社区

开发者社区> 被纵养的懒猫> 正文

有了四步解题法模板,再也不害怕动态规划! | 算法必看系列十六

简介: 动态规划的四步解题法其实是相互递进的,状态的定义离不开问题的拆解,递推方程的推导离不开状态的定义,最后的实现代码的核心其实就是递推方程,这中间如果有一个步骤卡壳了则会导致问题无法解决,当问题的复杂程度增加的时候,这里面的思维复杂程度会上升。用一句话解释动态规划就是 “记住你之前做过的事”,如果更准确些,其实是 “记住你之前得到的答案”。
+关注继续查看

原文链接

导言

动态规划问题一直是算法面试当中的重点和难点,并且动态规划这种通过空间换取时间的算法思想在实际的工作中也会被频繁用到,这篇文章的目的主要是解释清楚 什么是动态规划,还有就是面对一道动态规划问题,一般的 思考步骤 以及其中的注意事项等等,最后通过几道题目将理论和实践结合。

什么是动态规划

如果你还没有听说过动态规划,或者仅仅只有耳闻,或许你可以看看 Quora 上面的这个 回答。
image.png

How to explain dynamic

用一句话解释动态规划就是 “记住你之前做过的事”,如果更准确些,其实是 “记住你之前得到的答案”。

我举个大家工作中经常遇到的例子。

在软件开发中,大家经常会遇到一些系统配置的问题,配置不对,系统就会报错,这个时候一般都会去 Google 或者是查阅相关的文档,花了一定的时间将配置修改好。

过了一段时间,去到另一个系统,遇到类似的问题,这个时候已经记不清之前修改过的配置文件长什么样,这个时候有两种方案,一种方案还是去 Google 或者查阅文档,另一种方案是借鉴之前修改过的配置,第一种做法其实是万金油,因为你遇到的任何问题其实都可以去 Google,去查阅相关文件找答案,但是这会花费一定的时间,相比之下,第二种方案肯定会更加地节约时间,但是这个方案是有条件的,条件如下:

  • 之前的问题和当前的问题有着关联性,换句话说,之前问题得到的答案可以帮助解决当前问题
  • 需要记录之前问题的答案

当然在这个例子中,可以看到的是,上面这两个条件均满足,大可去到之前配置过的文件中,将配置拷贝过来,然后做些细微的调整即可解决当前问题,节约了大量的时间。

不知道你是否从这些描述中发现,对于一个动态规划问题,我们只需要从两个方面考虑,那就是 找出问题之间的联系,以及 记录答案,这里的难点其实是找出问题之间的联系,记录答案只是顺带的事情,利用一些简单的数据结构就可以做到。

思考动态规划问题的四个步骤

一般解决动态规划问题,分为四个步骤,分别是:

  • 问题拆解,找到问题之间的具体联系
  • 状态定义
  • 递推方程推导
  • 实现

这里面的重点其实是前两个,如果前两个步骤顺利完成,后面的递推方程推导和代码实现会变得非常简单。

这里还是拿 Quora 上面的例子来讲解,“1+1+1+1+1+1+1+1” 得出答案是 8,那么如何快速计算 “1+ 1+1+1+1+1+1+1+1”,我们首先可以对这个大的问题进行拆解,这里我说的大问题是 9 个 1 相加,这个问题可以拆解成 1 + “8 个 1 相加的答案”,8 个 1 相加继续拆,可以拆解成 1 + “7 个 1 相加的答案”,… 1 + “0 个 1 相加的答案”,到这里,第一个步骤 已经完成。

状态定义 其实是需要思考在解决一个问题的时候我们做了什么事情,然后得出了什么样的答案,对于这个问题,当前问题的答案就是当前的状态,基于上面的问题拆解,你可以发现两个相邻的问题的联系其实是 后一个问题的答案 = 前一个问题的答案 + 1,这里,状态的每次变化就是 +1。

定义好了状态,递推方程就变得非常简单,就是 dp[i] = dp[i - 1] + 1,这里的 dp[i] 记录的是当前问题的答案,也就是当前的状态,dp[i - 1] 记录的是之前相邻的问题的答案,也就是之前的状态,它们之间通过 +1 来实现状态的变更。

最后一步就是实现了,有了状态表示和递推方程,实现这一步上需要重点考虑的其实是初始化,就是用什么样的数据结构,根据问题的要求需要做那些初始值的设定。

public int dpExample(int n) {
// 多开一位用来存放 0 个 1 相加的结果
    int[] dp = new int[n + 1];  

    dp[0] = 0;      // 0 个 1 相加等于 0

    for (int i = 1; i <= n; ++i) {
        dp[i] = dp[i - 1] + 1;
    }

    return dp[n];
}

你可以看到,动态规划这四个步骤其实是相互递进的,状态的定义离不开问题的拆解,递推方程的推导离不开状态的定义,最后的实现代码的核心其实就是递推方程,这中间如果有一个步骤卡壳了则会导致问题无法解决,当问题的复杂程度增加的时候,这里面的思维复杂程度会上升。

来源 | 五分钟学算法
作者 | P.yh

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Python算法题解:动态规划解0-1背包问题
Python算法题解:动态规划解0-1背包问题
1017 0
多模态视频商品检索记录再刷新!第二届淘宝直播算法大赛完美落幕
多模态视频商品检索记录再刷新!第二届淘宝直播算法大赛完美落幕
21 0
15.如何自学Struts2之Struts2主题和模板[视频]
15.如何自学Struts2之Struts2主题和模板[视频]   之前写了一篇“打算做一个视频教程探讨如何自学计算机相关的技术”,优酷上传不了,只好传到百度云上:   http://pan.baidu.com/s/1kTDsa95 有问题可以直接回复这篇文章。
751 0
leetcode算法题解(Java版)-15-动态规划(斐波那契)
两种思路,都是递归。第一种是递归的判断每个节点的左右子树的深度是否只相差一以内。第二种做了剪枝处理,当判断到一个子树已经不满足时就返回结果。
2099 0
会员卡开卡表单模板配置(alipay.marketing.card.formtemplate.set)JAVA版本demo
官方接口文档:[url]https://docs.open.alipay.com/251/105668/[/url],我这里写的是开卡组件前两步的操作流程,仅供参考 1.调用接口前的准备工作(创建应用等)参考该文档:[url]https://docs.
706 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
4479 0
使用OpenApi弹性释放和设置云服务器ECS释放
云服务器ECS的一个重要特性就是按需创建资源。您可以在业务高峰期按需弹性的自定义规则进行资源创建,在完成业务计算的时候释放资源。本篇将提供几个Tips帮助您更加容易和自动化的完成云服务器的释放和弹性设置。
7751 0
560
文章
1795
问答
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载