menu

Algorithm Mr.How知其所以然之动态规划算法

Algorithm Mr.How知其所以然之动态规划算法

原创文章，版权所有，搬运文章，转发请注明polyaD，原文链接https://polyad.github.io/tags 如有任何问题或疑惑，请在后面留言或者发邮箱留言polyaluthor@gmail.com，加微信polyad或者qq数学算法开发10群 282642152进行探讨,请备注：Mr.How。

前言
  您好，欢迎来到我的引导学习记录笔记，我是polayD, Mr.How先生。本系列依据《怎样解题》，George Polya的方法以及知其所以然模式启发，进行拓展而成。希望在这里，您能找到引导式学习的快乐，逐步建立与形成自己的知识同化模式，摆脱碎片化信息的烦扰，掌握快速学习与深度知识系统化的技能，期待与您共同进步。
  信息碎片化的时代，随波逐流我们将一无所获，特别是当没有形成系统垂直化的知识模块，很多时候我们只能人云亦云，面对海量信息，无法判别重要性，相关性，有效性，普通的个人很难在信息洪流中找到自己的定位。深度式的知其所以然的引导式学习，可避开信息碎片化旋涡，同时突破信息茧房的束缚。下面波利亚将引领您，进入一个这个基础主题模块的海洋，带上自己的定位导航，抓紧好奇心的船舵，扬帆深入得在这片海洋里探索，前进，自我迭代进化。
**理念与标准设定迭代模块**
I.理念迭代：
1.缝合现实与理论的鸿沟。
2.缝合理论主题与练习的鸿沟。
3.认知升级：掌握方法论比掌握知识点更重要。
4.设立量化目标：标准框架与计划实施作业，建立模块化迭代。
5.潜意识出发平缓引导：第一人称为主，进行自我提问与引导，主要是让自我潜意识有参与感。
6.一根针插到底的解决问题：只要内心存在疑问，就应该把问题写入问题列表，随便再进行解读。彻底明白一个系统模块，胜过离散的弄清单个问题。
7.信息资源发散式归集：以此问题为核心支点，散发结合所有可能收集到的认知，整合解读，不唯教科书论，不唯单一信息来源论。尽量多查找一手资源。
8.问题全流程迭代：现实3D场景->发现问题->设立标准->提出问题->描述问题信息->解决问题->实践验证->抽象化->理论化->一般化->主题框架化->重新应用于新的3D场景。 9.导航路径：同类主题区别层面->理论层面->系列问题归集层面->实际问题解决层面 10.细节是魔鬼，细节决定了专业的高度
11.实现从0开始逐步构建到框架，从迭代框架实现知识的同化
12.算法是建立的数据结构上的操作，可以用不同的数据结构实现相同的结果
13.放下书本与答案，自我构建从0开始推导，用自己的理解写出来，标准是每一个小模块都是灵活使用。
14.先攻克最难的部分，再往易处走，如下山猛虎。带着问题，不断解析。最难部分要从易处着眼，从具体到逐步抽象，不断提出问题四面八方进行敲击，直到牢固。
15.主题系统如果是固化的，那说明只是在记忆，而不是理解与彻底掌握，必将一无所有。不以任何书本为准，而是以自我的知识构建为准，所有的资源都是为了自我知识构建服务，从第一性原理（从0）开始构建整个知识系统大厦。

II.标准与实施设定迭代：

 首先，做什么事之前，先要设定一下我们的小目标， 我们的整体导航路径： 1.主题解析，先难后易，深入浅出，案例拆解，举一反三。
2.主要解决两个问题：如何思考这个问题？如何使用这个解决问题？
3.尽可能所有收集参考资料，实践以后，再全部用自己的语言进行复述回答，将思路，事无巨细的写出来，特别是关键节点。
4.陆续将提供中英文版本。
5.问题解决同化迭代模式：理念与标准设定迭代模块，计划与实施迭代模块，路径框架迭代模块，问题引导列表分析迭代模块，执行分析步骤迭代模块，动画与代码实现迭代模块，方法工具归集迭代模块，反思批判迭代模块，十字定位迭代模块，意义与主题迭代模块，拓展应用迭代模块。
6.知识点主题模块同化迭代模式：理念与标准设定迭代模块，计划与实施迭代模块，路径框架迭代模块，意义背景迭代模块，十字定位迭代模块，问题引导列表分析迭代模块，区别迭代模块，反思批判迭代模块，拓展应用迭代模块。
计划与实施迭代模块
aq模块定位
  将如下基础算法主题模块化
穷举算法主题模块
递推算法主题模块
递归算法主题模块
迭代算法主题模块
贪婪算法主题模块
分支限界算法主题模块
分治法算法主题模块
回溯算法主题模块
动态规划算法主题模块 模拟算法主题模块
**掌握的路径框架**

目录

  • I 如何才算对这个动态规划算法知其所以然？
    • 1.寻找该动态规划算法的动态规划算法的意义
    • 这个动态规划算法怎么定义的？*
    • 为什么需要引入这个动态规划算法？
    • 这个动态规划算法解决了哪些问题？
    • 这个动态规划算法思维理论是什么？
    • 这个动态规划算法的数学原理是什么？
    • 这个动态规划算法的对自我定位？
    • 2.寻找该动态规划算法的原始出处
    • 这个动态规划算法的原始出处是哪里？
    • 这个动态规划算法的本质是什么？
    • 这个动态规划算法的解决问题的本质是什么？
    • 这个做法的本质又是什么？
    • 到底本质上是什么东西导致了这个做法如此？
    • 与这个问题类似的还有其它问题吗？
    • 这个动态规划算法是如何组成的？
    • 这个动态规划算法是如何一步一步推导出来的？
    • 3.回顾整个的思维过程细节
    • 动态规划算法的实现细节有哪些？
    • 如何自行分析推理出动态规划算法？
    • 能否回顾整个动态规划算法的思维过程细节？
    • 自己揣摩自己对这个动态规划算法的所有疑问：
      并列表：
    • 工具方法表
    • 为什么要这样（为什么这是好的）？
    • 为什么不是那样（有其它做法吗？有更好的做法吗？）？
    • 这样做是最好的吗？（为什么？能证明吗？）
    • 这个做法跟其它的什么做法有本质联系吗？
    • 这个跟这个的区别是什么？
    • 如何证明定理：看定理必看证明
    • 为什么这种动态规划算法是对的？
    • 为什么那种动态规划算法是错的？
    • 为什么这种动态规划算法不是最优的？
    • 证明为什么没有更优的动态规划算法。 —-
    • 4.反思反馈
    • 如何向一个4岁的小朋友解释这个算法？
    • 如何用一句话说出本质？
    • 如何在内心深处从0开始逻辑推理构建整个体系？
    • 能否一眼看出来？
    • 能否做到逻辑自洽？
      从理解开始，它的每一个细节都应该是完整而正确的，
      从各个方面考虑这个这个动态规划算法，找出与你已有知识之间的联系。
      考虑这个动态规划算法的细节，并尝试使它们尽可能地简单；
      总结你这个动态规划算法的方法，并且尝试把它用于其他问题。
    • 5.我们能得到什么
    • 更新潜意识系统
    • 升级思想思维系统
    • 归集工具方法系统
    • 理清概念区别系统
    • 整理案例问题系统
    • 经典好书与资源集
  • II.动态规划算法问题类型
    • 1.DP问题通用步骤及公式
    • 2.DP问题类别区分
    • 3.DP问题通用解题框架

引导回答

I 如何才算对这个动态规划算法知其所以然？

1.寻找该动态规划算法的动态规划算法的意义

这个动态规划算法怎么定义的？

  • 动态规划是一种问题优化技术，主要用于解决多阶段决策最优解问题。 （脑海里冒了一个泡：如何判断是否为多阶段决策问题？是否这种问题就存在最优解？）

为什么需要引入这个动态规划算法？

  • 主要是为了优化，通过存储过程中的结果，先实现空间上的优化，间接实现时间上的优化。因为动态规划问题的一般形式就是求最值，求最值的核心问题就是穷举。穷举可得出结果，但是过程可以优化。
    这个动态规划算法解决了哪些问题？

  • 用于计算机网络、路由、图形问题、计算机视觉、人工智能、机器学习,生物信息等领域。

这个动态规划算法思维理论是什么？

  • 多阶段决策问题+最优化。可拆分成小问题，小问题前面的结果，对后面的问题有影响。

这个动态规划算法的数学原理是什么？

  • 运筹学的分支与数学归纳法，为求解决策过程最优化的数学方法，一般是求其最值：求最大，求最小，求可不可行，求方案总数，求最多，求最少等。

这个动态规划算法的对自我定位？

  • 数学定位：高等数学->应用数学->运筹学->最优化理论； 数学相关：高等数学->离散数学->图论; 动态规划即广义马尔可夫模型

2.寻找该动态规划算法的原始出处
这个动态规划算法的原始出处是哪里？

  • 1956年，美国贝尔曼R.E.Bellman提出指导解决多阶段决策问题的最优化原理的数学方法。

这个动态规划算法的本质是什么？

  • 最优化原理的数学方法。动态规划算法的策略迭代、值迭代基于贝尔曼方程。

这个动态规划算法的解决问题的本质是什么？

  • 可求出多阶段决策问题的整体最优解，先解决问题，再做出选择问题的解，包含局部最优解，但不是每个阶段都是最优解，会记录之前的所有最优解，最后得出整体最优解。动态规划算法：解决问题->结果->做出选择->符合条件加入备忘，不符合条件，撤销选择，回到选择前->合并每个阶段的结果得到全局最优解。

这个做法的本质又是什么？

  • 已知的多阶段决策模型，找出每一个阶段的可能最优解，最后做出选择。

  • 两个数组的填充游戏，在现有数组上，重新构建一个结果数组，然后进行结果填充，再根据绘图空间上的优化

到底本质上是什么东西导致了这个做法如此？

  • 递归，备案式记录结果。递归得出结果，做出选择，不符合条件再回撤。备案式记录结果，得到每个决策阶段的结果，得到全局最优的解

与这个问题类似的还有其它问题吗？

  • 贪心算法，解由多阶段组成，并且前一个问题决策，只做局部最优解，再进行下一阶段问题的求解，最终结果不一定能得到全局最优解

  • 分治算法，解由多个问题部分组成，每个问题部分都是独立的，各自独立的解，将解进行合并

这个动态规划算法是如何组成的？

  • 先识别是否动态规划问题，是否可以使用动态规划技术优化？先计算出第0项到第6或10项的每一项的结果。找出边界，并探索状态转移方程。确认基准条件，先用递归实现，再用迭代或备忘录优化，优化复杂度。

这个动态规划算法是如何一步一步推导出来的？

3.回顾整个的思维过程细节

动态规划算法的实现细节有哪些？

如何自行分析推理出动态规划算法？

能否回顾整个动态规划算法的思维过程细节？

自己揣摩自己对这个动态规划算法的所有疑问：

  并列表：      * > 局部最优与全局最优，动态规划的关系     * > 后效性-有或无后效性。无后效性：当前阶段决策问题的结果，只与当前状态有关，不影响后一个阶段决策问题。有后效性：

  • 问题维度：一维问题，二维问题，三维问题？

  • 工具方法
    为什么要这样（为什么这是好的）？
    为什么不是那样（有其它做法吗？有更好的做法吗？）？
    这样做是最好的吗？（为什么？能证明吗？）
    这个做法跟其它的什么做法有本质联系吗？
    这个跟这个的区别是什么？
    如何证明定理：看定理必看证明
    为什么这种动态规划算法是对的？
    为什么那种动态规划算法是错的？
    为什么这种动态规划算法不是最优的？
    证明为什么没有更优的动态规划算法。

4.反思反馈

如何向一个4岁的小孩解释？

  • 可递归：问题变小，问题的解法不变。选择，合并，

如何用一句话说出本质？

能否一眼看出来？

能否做到逻辑自洽？

  • 从理解开始，它的每一个细节都应该是完整而正确的，    
从各个方面考虑这个这个动态规划算法，找出与你已有知识之间的联系。    
考虑这个动态规划算法的细节，并尝试使它们尽可能地简单；    
总结你这个动态规划算法的方法，并且尝试把它用于其他问题。

5.我们能得到什么

更新潜意识系统

  • 先辨别是否是最优化问题，是否符合动态规划特征

升级思想思维系统

归集工具方法系统

  • 回退技术，如何实现回退？

  • 选择技术，如何实现选择？ min,max,sum等自定义函数

  • 合并技术，如何将结果向上合并？ 向上合并，实际上是递归函数嵌套

  • 分解技术，如何将问题逐步分解？

  • 记忆化递归技术 。 记忆化递归技术，创建另外一个数据结构，保存数据

  • 备忘录技术，如何将问题的解置入备忘录，如何将问题的解从备忘录提出？

  • 递归技术，如何将问题规模不断缩小？

  • 自顶向下技术，如何实现自顶向下技术？

  • 自底向上技术，如何实现自底向上技术？

  • 优化技术，如何实现时间与空间复杂度的优化？

  • 迭代技术，如何将递归技术快速转变成迭代技术实现？

  • 滚动数组技术， 滚动数组，是只保存有关的数据，不做全部保存。二维压缩为一维。

  • 如何确定临界条件？ 推向极端情况

  • 如何确定状态转移方程？ 分类讨论，再合并

  • 如何枚举状态？

  • 如何定义结果项？一个是函数f(n)，一个是项 dp[][]

  • 动态规划解题框架： ``` DP问题通用解题框架引导
    我能否判断这是个动态规划问题？
    1.是否有接触过类似题目？ 2.是否多阶段，有重叠子，最优子结构，无后效性。 阶段之间：多个途径到达;重叠子:可以用递归;最优子结构：需要做最优选择;无后效性：可备忘录式优化。 3.先用递归算法解决，再考虑用动态规划逐步优化。动态规划流程：递归的暴力解法 -> 带备忘录的递归解法 -> 非递归的动态规划解法。

能否按照递归步骤实现？

  • 递归规划版本，源自于数学归纳法，属于数学证明。
    递归规划的四大步骤:状态定义->状态之间的关系->初始状态的安全边界->画图优化
    第一步骤：定义数组元素的含义
    第二步骤：画图找出数组元素之间的关系式
    利用历史数据来推出新的元素值，即找出数组元素之间的关系式。
    第三步骤：找出初始值，确定安全边界
    有了初始值，并且有了数组元素之间的关系式，就可以得到 dp[n] 的值。 第四步骤：画图优化
    时间与空间复杂度优化

能否按照动态规划步骤实现？ 动态规划的四大步骤：状态定义->状态之间的关系->初始状态的安全边界->画图优化 第一步骤：定义数组元素的含义
dp[i] 是代表什么意思？ 第二步骤：画图找出数组元素之间的关系式
利用历史数据来推出新的元素值，即找出数组元素之间的关系式。
第三步骤：找出初始值，确定安全边界
有了初始值，并且有了数组元素之间的关系式，就可以得到 dp[n] 的值。 第四步骤：画图优化
空间复杂度优化
二维矩阵优化成一维矩阵
画二维 dp 的矩阵图，然后看元素之间的值依赖
```

理清概念区别系统

整理案例问题系统

经典好书与资源集

II.动态规划算法问题类型

1.DP问题通用步骤及公式

  • 2.DP问题类别区分 一维 DP
    二维数组的 DP

  • 走楼梯问题

  • 最大连续子序列之和

  • *数塔问题（二叉树从上往下遍历最大和问题）

  • 01背包问题

  • 最长递增子序列(LIS)

  • 最长公共子序列(LCS)

#参考资料
—–
一级资料文献与书籍及重要作者
文献：
书籍：
1.《怎样解题》，作者，George Polya
博客：
论坛：
视频：

二级资料：他人加工且有观点及大众资料
博客： 1.”知其所以然（以算法学习为例）” 作者，刘未鹏 http://mindhacks.cn/2008/07/07/the-importance-of-knowing-why/
2.Dynamic Programming Summary
3.动态规划 论坛：
视频：

返回顶部

评论：

技术文章推送

知其所以然主题模块分享

微信搜索公众号: How先生polyad
wechat 微信公众号：How先生polyad