数据结构与算法之美
王争
前 Google 工程师
283752 人已学习
新⼈⾸单¥68
登录后,你可以任选4讲全文学习
课程目录
已完结/共 81 讲
基础篇 (38讲)
数据结构与算法之美
15
15
1.0x
00:00/00:00
登录|注册

41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题

无重复子问题
最优解问题
重复子问题
无后效性
最优子结构
重复子问题
穷举搜索
贪心选择性
无后效性
最优子结构
动态规划代码实现
状态转移方程
最优子结构
动态规划代码实现
重复子问题
递归树
回溯算法
重复子问题
无后效性
最优子结构
多阶段决策最优解模型
分治算法
动态规划算法
回溯算法
贪心算法
状态转移方程法
状态转移表法
矩阵最短路径问题
重复子问题
无后效性
最优子结构
多阶段决策最优解模型
硬币找零问题
四种算法思想比较分析
两种动态规划解题思路
一个模型三个特征实例剖析
一个模型三个特征
课后思考
动态规划原理

该思维导图由 AI 生成,仅供参考

上一节,我通过两个非常经典的问题,向你展示了用动态规划解决问题的过程。现在你对动态规划应该有了一个初步的认识。
今天,我主要讲动态规划的一些理论知识。学完这节内容,可以帮你解决这样几个问题:什么样的问题可以用动态规划解决?解决动态规划问题的一般思考过程是什么样的?贪心、分治、回溯、动态规划这四种算法思想又有什么区别和联系?
理论的东西都比较抽象,不过你不用担心,我会结合具体的例子来讲解,争取让你这次就能真正理解这些知识点,也为后面的应用和实战做好准备。

“一个模型三个特征”理论讲解

什么样的问题适合用动态规划来解决呢?换句话说,动态规划能解决的问题有什么规律可循呢?实际上,动态规划作为一个非常成熟的算法思想,很多人对此已经做了非常全面的总结。我把这部分理论总结为“一个模型三个特征”。
首先,我们来看,什么是“一个模型”?它指的是动态规划适合解决的问题的模型。我把这个模型定义为“多阶段决策最优解模型”。下面我具体来给你讲讲。
我们一般是用动态规划来解决最优问题。而解决问题的过程,需要经历多个决策阶段。每个决策阶段都对应着一组状态。然后我们寻找一组决策序列,经过这组决策序列,能够产生最终期望求解的最优值。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

本文深入介绍了动态规划的原理和应用,通过“一个模型三个特征”理论和具体实例剖析,全面阐述了动态规划的解题思路。首先,文章介绍了动态规划适合解决的问题模型,详细解释了最优子结构、无后效性和重复子问题这三个特征。随后,通过一个具体的动态规划问题,展示了如何应用“一个模型三个特征”来分析问题的适用性。文章还总结了动态规划解题的两种思路,即状态转移表法和状态转移方程法。状态转移表法通过填表的方式解决问题,而状态转移方程法则通过递归公式求解。两种方法各有特点,读者可以根据具体问题选择合适的解题思路。整体而言,本文通过深入浅出的方式,全面介绍了动态规划的理论知识和解题思路,对读者快速了解动态规划原理具有重要指导意义。 文章还对比了贪心、回溯、动态规划和分治四种算法思想,指出它们之间的联系和区别。贪心、回溯、动态规划可以归为一类,都适用于多阶段决策最优解模型,而分治算法则不太适合抽象成多阶段决策模型。此外,文章还提到了动态规划的特点和适用条件,强调了动态规划的高效性和解决问题的限制条件。最后,文章鼓励读者多思考、多练习,指出理论知识需要通过实际练习才能真正理解和应用。 总的来说,本文通过理论知识和实际问题的结合,为读者提供了全面的动态规划学习指南,帮助读者快速理解动态规划原理和解题思路,为实际问题的解决提供了重要的指导和启发。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《数据结构与算法之美》
新⼈⾸单¥68
立即购买
登录 后留言

全部留言(168)

  • 最新
  • 精选
  • yaya
    可以看做爬阶梯问题,分别可以走1.3.5步,怎么最少走到9步,动态转移方程为f(9)=1+min(f(8),f(6),f(4))

    作者回复: 👍

    2019-01-03
    27
    345
  • feifei
    经过一个星期的努力,这个动态规划终于有点感觉了,今天来做题,我也来试试解这个题目,在看了第一个童鞋的解法后,感觉这个写的太死了,再就是没有反推出哪些币的组合,我就自己来实现了下! 我也想说动态规划的解,真不容易啊,我按照老师提供的方法,先使用回塑写出了暴力搜索,然后再画出了递归树,找到状态组合,然后才来写这个动态规划,感觉好复杂,不过吧,这个使用状态转移方程,我感觉更难,比这个递归还难写。。。。。。,最主要是这个状态想不到,但这个动态规划代码写完了,我又感觉能写方程了,我想哭。。。。。。。 public int countMoneyMin(int[] moneyItems, int resultMemory) { if (null == moneyItems || moneyItems.length < 1) { return -1; } if (resultMemory < 1) { return -1; } // 计算遍历的层数,此按最小金额来支付即为最大层数 int levelNum = resultMemory / moneyItems[0]; int leng = moneyItems.length; int[][] status = new int[levelNum][resultMemory + 1]; // 初始化状态数组 for (int i = 0; i < levelNum; i++) { for (int j = 0; j < resultMemory + 1; j++) { status[i][j] = -1; } } // 将第一层的数数据填充 for (int i = 0; i < leng; i++) { status[0][moneyItems[i]] = moneyItems[i]; } int minNum = -1; // 计算推导状态 for (int i = 1; i < levelNum; i++) { // 推导出当前状态 for (int j = 0; j < resultMemory; j++) { if (status[i - 1][j] != -1) { // 遍历元素,进行累加 for (int k = 0; k < leng; k++) { if (j + moneyItems[k] <= resultMemory) { status[i][j + moneyItems[k]] = moneyItems[k]; } } } // 找到最小的张数 if (status[i][resultMemory] >= 0) { minNum = i + 1; break; } } if (minNum > 0) { break; } } int befValue = resultMemory; // 进行反推出,币的组合 for (int i = minNum - 1; i >= 0; i--) { for (int j = resultMemory; j >= 0; j--) { if (j == befValue) { System.out.println("当前的为:" + status[i][j]); befValue = befValue - status[i][j]; break; } } } return minNum; }

    作者回复: 👍 都有这个似懂非懂的过程的 多练习 慢慢就有感觉了

    2019-01-06
    3
    32
  • 煦暖
    状态转移表法,二维状态表的图中,第一行下面的表达式: 文中“min(4+3, 8+3)”应该是“min(4+3, 9+3)”

    作者回复: 嗯嗯 是的 笔误 抱歉

    2019-01-03
    14
  • 阿崔cxr
    老师,我按照文章里面的代码敲了一遍, 状态转移表法的那个代码运行结果等于 等于19 状态转移方程法的那个代码运行结果等于 18 不知道大家是不是这样的??????

    作者回复: 我擦,我研究下

    2019-02-21
    2
    4
  • blacknhole
    状态转移方程法的代码实现有问题: 1,int minUp = Integer.MIN_VALUE;语句应赋值为Integer.MAX_VALUE。 2,返回前应将返回值赋值给mem[i][j]。

    作者回复: 已改 多谢指正

    2018-12-31
    4
  • farFlight
    用动态规划的方法,初始化那些等于币值的价值,然后从1开始一步一步推到w元,f(k)代表k元时最少的硬币数量,状态方程是: f(k) = min(f(k-vi)) + 1, i需要遍历所有的币种。 另外,请问老师之后会多讲一些回溯的技巧吗?回溯方法虽然本身复杂度比较高,但是可以用一些剪枝技巧branch and bound,这样实际运行时间也能很快,而且很多复杂的问题用回溯法思路会比较简单。

    作者回复: 高级篇会讲到

    2018-12-31
    3
  • 大家做动态规划题目时会出现这种情况吗?在没看这些理论的知识时,不管什么最优子结构,重复子问题,也不管什么状态的时候,有些简单的问题自己还能解决,直到了解了这些知识,知道了什么是动态规划,了解了动态规划中状态转移的概念之后,我们往往在一个特别简单的问题上就去分析的很复杂以至于以前感觉很简单的问题现在都不会解了,感觉越做越不会了。。。

    作者回复: 我讲解主要是从由来、本质来讲,不是特别target面试切题的。切题的话直接写状态转移方程就好了,不用理解的那么透彻!

    2019-06-15
    1
  • Zix
    老师,回溯的那种解法,代码有问题,会出现数组越界,边界的问题。

    作者回复: 嗯嗯 我再去看下

    2019-02-26
    1
  • 为什么说存在重复子问题会更适合尝试动态规划来解决

    作者回复: 再看下文章吧,文章里已经讲到了

    2019-10-28
  • 未来的胡先森
    小争哥,文章「状态转移方程法」中的代码,int minLeft = Integer.MAX_VALUE、int minUp = Integer.MAX_VALUE 是否存在问题。当计算到达(1,0)、(0,1) 两个点时,左右路径会变成初始的值,导致后续计算全部出错,是不是该初始化为 matrix[0] [0] 呢? 这是我照着你思路实现的代码: ```java int[][] memo = null, matrix = null; public int minDistance2(int[][] matrix){ int len = matrix.length; this.matrix = matrix; // 转移方程法 memo = new int[len][len]; return minDistanceCore(len - 1, len - 1); } private int minDistanceCore(int row,int col) { if (row == 0 && col == 0) { // (0,0) 直接返回值 return matrix[0][0]; } if (memo[row][col] != 0) { // 若已计算则直接返回对应值 return memo[row][col]; } int distLeft = matrix[0][0], distUp = matrix[0][0]; if (col > 0) { distLeft = minDistanceCore(row, col - 1); } if (row > 0) { distUp = minDistanceCore(row - 1, col); } int curDist = matrix[row][col] + Integer.min(distLeft, distUp); memo[row][col] = curDist; // 记录当前距离 return curDist; } ```

    作者回复: 不好意思,才回复你,我上周回了趟老家。你说的没错,是有点问题。不过,你的两条回复我都看了,感觉初始化方式也不大对。我一会重新写下代码,更新上去。 修改回复:我又重新看了下代码,貌似没问题哈😂,你能给我一个你觉得有问题的测试用例吗?

    2019-08-18
收起评论
显示
设置
留言
99+
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部