动态规划答疑篇

-----------

这篇文章就给你讲明白两个问题:

1、到底什么才叫「最优子结构」,和动态规划什么关系。

2、为什么动态规划遍历 dp 数组的方式五花八门,有的正着遍历,有的倒着遍历,有的斜着遍历。

一、最优子结构详解

「最优子结构」是某些问题的一种特定性质,并不是动态规划问题专有的。也就是说,很多问题其实都具有最优子结构,只是其中大部分不具有重叠子问题,所以我们不把它们归为动态规划系列问题而已。

我先举个很容易理解的例子:假设你们学校有 10 个班,你已经计算出了每个班的最高考试成绩。那么现在我要求你计算全校最高的成绩,你会不会算?当然会,而且你不用重新遍历全校学生的分数进行比较,而是只要在这 10 个最高成绩中取最大的就是全校的最高成绩。

我给你提出的这个问题就符合最优子结构:可以从子问题的最优结果推出更大规模问题的最优结果。让你算每个班的最优成绩就是子问题,你知道所有子问题的答案后,就可以借此推出全校学生的最优成绩这个规模更大的问题的答案。

你看,这么简单的问题都有最优子结构性质,只是因为显然没有重叠子问题,所以我们简单地求最值肯定用不出动态规划。

再举个例子:假设你们学校有 10 个班,你已知每个班的最大分数差(最高分和最低分的差值)。那么现在我让你计算全校学生中的最大分数差,你会不会算?可以想办法算,但是肯定不能通过已知的这 10 个班的最大分数差推到出来。因为这 10 个班的最大分数差不一定就包含全校学生的最大分数差,比如全校的最大分数差可能是 3 班的最高分和 6 班的最低分之差。

这次我给你提出的问题就不符合最优子结构,因为你没办通过每个班的最优值推出全校的最优值,没办法通过子问题的最优值推出规模更大的问题的最优值。前文「动态规划详解」说过,想满足最优子结,子问题之间必须互相独立。全校的最大分数差可能出现在两个班之间,显然子问题不独立,所以这个问题本身不符合最优子结构。

那么遇到这种最优子结构失效情况,怎么办?策略是:改造问题。对于最大分数差这个问题,我们不是没办法利用已知的每个班的分数差吗,那我只能这样写一段暴力代码:

int result = 0;for (Student a : school) {    for (Student b : school) {        if (a is b) continue;        result = max(result, |a.score - b.score|);    }}return result;

改造问题,也就是把问题等价转化:最大分数差,不就等价于最高分数和最低分数的差么,那不就是要求最高和最低分数么,不就是我们讨论的第一个问题么,不就具有最优子结构了么?那现在改变思路,借助最优子结构解决最值问题,再回过头解决最大分数差问题,是不是就高效多了?

当然,上面这个例子太简单了,不过请读者回顾一下,我们做动态规划问题,是不是一直在求各种最值,本质跟我们举的例子没啥区别,无非需要处理一下重叠子问题。

前文不同定义不同解法 就展示了如何改造问题,不同的最优子结构,可能导致不同的解法和效率。

PS:我认真写了 100 多篇原创,手把手刷 200 道力扣题目,全部发布在 labuladong的算法小抄,持续更新。建议收藏,按照我的文章顺序刷题,掌握各种算法套路后投再入题海就如鱼得水了。

再举个常见但也十分简单的例子,求一棵二叉树的最大值,不难吧(简单起见,假设节点中的值都是非负数):

int maxVal(TreeNode root) {    if (root == null)        return -1;    int left = maxVal(root.left);    int right = maxVal(root.right);    return max(root.val, left, right);}

你看这个问题也符合最优子结构,以 root 为根的树的最大值,可以通过两边子树(子问题)的最大值推导出来,结合刚才学校和班级的例子,很容易理解吧。

当然这也不是动态规划问题,旨在说明,最优子结构并不是动态规划独有的一种性质,能求最值的问题大部分都具有这个性质;但反过来,最优子结构性质作为动态规划问题的必要条件,一定是让你求最值的,以后碰到那种恶心人的最值题,思路往动态规划想就对了,这就是套路。

动态规划不就是从最简单的 base case 往后推导吗,可以想象成一个链式反应,以小博大。但只有符合最优子结构的问题,才有发生这种链式反应的性质。

找最优子结构的过程,其实就是证明状态转移方程正确性的过程,方程符合最优子结构就可以写暴力解了,写出暴力解就可以看出有没有重叠子问题了,有则优化,无则 OK。这也是套路,经常刷题的朋友应该能体会。

这里就不举那些正宗动态规划的例子了,读者可以翻翻历史文章,看看状态转移是如何遵循最优子结构的,这个话题就聊到这,下面再来看另外个动态规划迷惑行为。

二、dp 数组的遍历方向

我相信读者做动态规问题时,肯定会对 dp 数组的遍历顺序有些头疼。我们拿二维 dp 数组来举例,有时候我们是正向遍历:

int[][] dp = new int[m][n];for (int i = 0; i < m; i  )    for (int j = 0; j < n; j  )        // 计算 dp[i][j]

有时候我们反向遍历:

for (int i = m - 1; i >= 0; i--)    for (int j = n - 1; j >= 0; j--)        // 计算 dp[i][j]

有时候可能会斜向遍历:

// 斜着遍历数组for (int l = 2; l <= n; l  ) {    for (int i = 0; i <= n - l; i  ) {        int j = l   i - 1;        // 计算 dp[i][j]    }}

甚至更让人迷惑的是,有时候发现正向反向遍历都可以得到正确答案,比如我们在「团灭股票问题」中有的地方就正反皆可。

那么,如果仔细观察的话可以发现其中的原因的。你只要把住两点就行了:

1、遍历的过程中,所需的状态必须是已经计算出来的

2、遍历的终点必须是存储结果的那个位置

下面来距离解释上面两个原则是什么意思。

比如编辑距离这个经典的问题,详解见前文「编辑距离详解」,我们通过对 dp 数组的定义,确定了 base case 是 dp[..][0]dp[0][..],最终答案是 dp[m][n];而且我们通过状态转移方程知道 dp[i][j] 需要从 dp[i-1][j], dp[i][j-1], dp[i-1][j-1] 转移而来,如下图:

那么,参考刚才说的两条原则,你该怎么遍历 dp 数组?肯定是正向遍历:

for (int i = 1; i < m; i  )    for (int j = 1; j < n; j  )        // 通过 dp[i-1][j], dp[i][j - 1], dp[i-1][j-1]        // 计算 dp[i][j]

因为,这样每一步迭代的左边、上边、左上边的位置都是 base case 或者之前计算过的,而且最终结束在我们想要的答案 dp[m][n]

再举一例,回文子序列问题,详见前文「子序列问题模板」,我们通过过对 dp 数组的定义,确定了 base case 处在中间的对角线,dp[i][j] 需要从 dp[i 1][j], dp[i][j-1], dp[i 1][j-1] 转移而来,想要求的最终答案是 dp[0][n-1],如下图:

这种情况根据刚才的两个原则,就可以有两种正确的遍历方式:

要么从左至右斜着遍历,要么从下向上从左到右遍历,这样才能保证每次 dp[i][j] 的左边、下边、左下边已经计算完毕,得到正确结果。

现在,你应该理解了这两个原则,主要就是看 base case 和最终结果的存储位置,保证遍历过程中使用的数据都是计算完毕的就行,有时候确实存在多种方法可以得到正确答案,可根据个人口味自行选择。

来源:https://www.icode9.com/content-4-753151.html

(0)

相关推荐

  • 万字长文,佩奇算法八大思想!

    零.前言 大家好,我是小浩. 分享一篇由读者 @Kevin_涛 写的算法思想文章: 在讲解八大算法思想之前我想先简述以下三个问题,以便大家更好的理解算法. 1. 什么是算法? <算法导论> ...

  • 动态规划(DP)

    本课程是从少年编程网转载的课程,目标是向中学生详细介绍计算机比赛涉及的编程语言,数据结构和算法.编程学习最好使用计算机,请登陆 www.3dian14.org (免费注册,免费学习). 本月7月13日 ...

  • 动态规划详解

    这篇文章是我们号半年前一篇 200 多赞赏的成名之作 动态规划详解 的进阶版.由于账号迁移的原因,旧文无法被搜索到,所以我润色了本文,并添加了更多干货内容,希望本文成为解决动态规划的一部「指导方针」. ...

  • Python|最大子序和

    前言最大字序和的思想用到了动态规划思想,本文章通过最大字序和例子来简单解释动态规划思想.动态规划指的是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推的方式去解决,就是将待求解的问题分解 ...

  • 这个前端竟然用动态规划写瀑布流布局?给我打死他!

    前言 瀑布流布局是前端领域中一个很常见的需求,由于图片的高度是不一致的,所以在多列布局中默认布局下很难获得满意的排列. 我们的需求是,图片高度不规律的情况下,在两列布局中,让左右两侧的图片总高度尽可能 ...

  • 狂刷100道题,我是怎么向5岁侄女解释动态规划的? | 掘金年度征文

    我膨胀了,相信看了这个标题的同学,肯定忍不住破口大骂,什么瓜皮哦,dynamic programming这么简单吗,在我的印象里,尼玛动态规划是最难的. 背景 侄女5岁现在开始学习加减法了,每次做数学 ...

  • 经典动态规划:0-1 背包问题

    前言 经过前面三篇动态规划文章的介绍,相信大家对动态规划.分治.贪心有了充分的理解,对动态规划的 3 个核心问题.其本质也有了了解. 纸上得来终觉浅,绝知此事要躬行. 那么今天开始我们来聊聊具体的那些 ...

  • (1条消息) 动态规划就此一篇 全网最详细, 逐步理解, 万字总结

    文章目录 动态规划 - 超详细系列 首先,先大致列下这篇文章会讲到什么 1.相较于暴力解法,动态规划带给我们的是什么?为什么会有重叠子问题以及怎么去避免的? 2.用不同难度的动态规划问题举例说明, 最 ...

  • 2017麦芽初中夏令营之志愿者答疑篇

    自三月中旬麦芽发布2017麦芽夏令营招募以来,承蒙海洋大学北辰青年社团帮助推广,已有不少的志愿者报名,那么,针对于志愿者的一些问题,我在这里做一个简单的回答,同时友情提醒一下,志愿者报名截止时间是5月 ...

  • 麦芽冬夏令营 | 志愿者答疑篇

    每当麦芽的冬夏令营来临时,总会有一些新朋友有不少的疑问,借2018麦芽夏令营之际,就来一次"系统性"回复吧. 问:麦芽是一个什么样的组织? 答:麦芽是一个纯公益的,由民间热心公益阅 ...

  • 麦芽冬夏令营|志愿者答疑篇

    每当麦芽的冬夏令营来临时,总会有一些新朋友有不少的疑问,借2018麦芽夏令营之际,就来一次"系统性"回复吧. 问:麦芽是一个什么样的组织? 答:麦芽是一个纯公益的,由民间热心公益阅 ...

  • 松针食用答疑篇---附松针酵素的制作

    松针食用答疑篇 [1]问:哪些松针可以食用? 答:我这10几年用的最多的松针品种是:马尾松.油松.五针松.白皮松.它们长什么样子可以查询百度. (下面这篇文章,帮助您更好认识他们) 教你认识4种食用松 ...

  • 投稿 | 考研复习经验之数学答疑篇

    作者 | 小凯 " " 数学答疑 1.数学老师的选择. 答:高数这一块跟汤家凤和张宇.把他们的课多听一听,汤神的课适合夯实基础,而且他人真的超好,满满的正能量.宇哥的课适合进一步的 ...

  • 答疑篇:中企组织管理的尴尬、困惑、成因及出路

    导读:中企当下的组织管理究竟好还是差?光鲜的业绩与混乱的管理不矛盾吗?为什么那些外企之间很相似,而与我们中企都相反?是他们傻还是我们错了?尴尬的现状让很多人心存困惑.那如何判定我们的管理水平呢?这一切 ...

  • 随势向北答疑篇

    随势向北答疑篇

  • 聊聊在家赚钱的一些机会:实践答疑篇

    无论什么领域,只要你问堂主就敢答. 今天是周六,又到了堂主喜欢的你问我答环节,大家的提问也比较实在,我们不只是讲对的话,更要解决具体遇到问题. 我把知识分为两种,一种是通过思辨获得,一种只能通过行动获 ...

  • 练习瑜伽常见热门问题答疑篇

    秘书长宣传专栏 中国国际太极·瑜伽大会 广东省江门市秘书长:钟艳珍(菜菜)   一.运动和按摩的区别 长期按摩肉会越来越松最后肌肉无力,松弛下垂 长期运动带来好的身材紧实的肌肉与柔韧兼备,肌肉与弹性都 ...