全球快资讯：算法之动态规划算法简介

来源: 阿杰科技说 ┆ 时间: 2022-08-05 09:41:57

动态规划概述

(相关资料图)

算法，是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。在现实生活中，算法具有如下一些特征：

有穷性：指算法必须能在执行有限个步骤之后终止。

确切性：算法的每一步骤必须有确切的定义。

可行性：算法中执行的任何计算步骤都是可以被分解为基本的可执行操作步骤，即每个计算步骤都可以在有限的时间内完成。

输入项：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定义除了初始条件。

输出项：一个算法有1个或多个输出，以反映对输入数据加工后的结果，没有输出的算法是无意义的。

在软件行业中，算法是基⽯，没有算法的软件是没有灵魂的，小到排序、遍历、查找、搜索，大到动态规划、贪心算法，都可以看到算法的影子。算法的稳定与否直接决定了软件的质量。而我们今天需要重点讲的动态规划其实就占据了很⼤的⽐重。

当很多⼈⾯对复杂的算法问题时，总是缺乏清晰的解题思路，有时候这种阻碍会从⾯试延伸⾄晋升。在算法领域，动态规划往往是解决问题的重要⽅法论，许多问题都可以使用它得到解决，并且它在处理大量数据时可以有效降低时间复杂度，提升软件的性能。再加上，通过动态规划问题还能很好地考察⼀个技术⼈的数学模型抽象能⼒和逻辑思维能⼒，进而很好地反应个⼈在算法上的综合能⼒。所以，在很多大厂的⾯试中，都会看到动态规划相关问题。

既然，动态规划有一定的学习成本和难度，那具体需要怎么系统学习来掌握它呢？其实，和很多的软件编写过程一样，动态规划也是有套路可寻的，以下是全⽂。

在正式开始动态规划算法之前，让我们先来看几个场景：

那个问题看起来好像可以使⽤递归，但是我该怎么遍历整个数据结构呢？

这个问题看起来需要穷举，但排列组合好像挺难的……

这⾥的排列组合情况实在太多了，我到底该怎么优化时间复杂度？

其实，⼏乎所有⼈在初学算法和动态规划时都会有这种感受，特别是当待解决的问题步⼊“穷举”这个领域时。事实上，穷举从来都不是⼀个好的解决⽅案，因为很多的场景是无法使用“穷举”这种方式来完成的。因此，针对这类问题的求解⽅法真是⼋仙过海、各显神通，我们很难直接从这些解法中找到规律，同时这些解法⼜晦涩难懂。

事实上，数据结构和算法虽然从表⾯上看纷繁复杂，但常⽤的基本思想和⽅法其实就那么几种。并且，这些简单的思路和方法，同样适⽤于动态规划问题，因此，只要我们掌握了正确的学习⽅法，形成经验式总结，那么当我们再去⾯对看似“⽞幻”的动态规划问题时，也不是什么难事。

对于动态规划，我会把一些学习窍⻔、遇到的问题和解题思路，进⾏归纳总结，进而梳理出⼀条清晰的路径，最终形成一个系列的文章。相信学习此系列文章之后，读者将会收获清晰的解题思路，从而轻松跨过⼤⼚算法⾯试这道坎。

建⽴扎实的基础知识体系

⾸先，我想强调的是，我们需要先掌握基础数据结构和算法，然后再来谈动态规划。动态规划不仅名字听起来⼗分⾼级，它也的确是⼀种⾼级的解决问题的思想。为了更好地理解这个思想，掌握基础数据结构就显得尤为重要了，⽐如⾼维数组这样的数据结构，就经常出现在动态规划解法当中。其次是算法，像是递归、搜索和迭代这些常⻅的算法，都会作为⼯具在动态规划解法中使⽤。所以说，掌握基础数据结构和算法，就是学习动态规划的基⽯，怎样强调其重要性都不过分。

其次，我还需要强调一点，和编码一样，算法需要通过编码才能得到提升，请不要忽视实践的⼒量。我曾不⽌⼀次在⾯试环节中，看到⾯试者在⽩板上纠结于这样的问题：我是否该在循环上加上等号这个条件。所以在平时学习、练习的过程中，就需要要重视细节、重视细节、重视细节，做到心中有数。

透彻理解动态规划的基本⽅法论

前文说过，动态规划并不单指某种算法，而是⼀种思想。我们说算法是⼀种简单的经验总结和套路。那什么是思想呢？相较于算法，思想更多的是指导你我来解决问题的。既然是思想，那这个东⻄就⽐较难落实到实践上来。

为此，我们必须找到⼀些规律，来指导我们解决动态规划问题。这些规律或特征包括：寻找⼦问题、递归求解、重叠⼦问题与⽆后效性、状态存储。如果你完全没有接触过动态规划，你可能会觉得这⼏个词已经够头疼了，但如果你接触过，那么它们就会很简单。

最后，在理解这些概念及其背后的深意之后，我们需要对其进⾏归纳总结。这么做的主要⽬的在于，你可以拥有⼀个清晰的判断标准：哪些问题应该使⽤动态规划来解，⽽哪些不应该或不能使⽤动态规划来解。避免盲⽬地使⽤动态规划来解题，弄清楚这个问题后，我们才能有的放⽮地解决算法难题。

学会总结解题思路

掌握经典的动态规划问题特别重要，因为很多问题都是从这些经典问题延伸出来的，在后⾯的文章中，我会重点介绍这些经典的动态规划问题。在你掌握了诸如背包问题、⼦序列问题或⼦数组问题之后，你就会发现这些问题都可以进⾏归纳总结。

事实上，几乎90% 以上的情况下都是可以通过总结归纳来实现的，并且这些经验⼗分适合⽤来应对⾯试。所以，我希望在接下来的学习过程中，大家建⽴⾃⼰的经验总结，并形成自己的经验套路。

其次，在面试前，还需要刷一些常见的算法题，不过刷题也要讲究⼀个度，我当然希望你能够轻松应对国内⼤⼚或国际⼤⼚的算法⾯试环节，但是你还是应该循序渐进，慢慢提升刷题数量和刷题的题⽬难度。正所谓欲速则不达！只有把每⼀道题⽬吃透，形成自己对题目的思考，才能在未来复习的过程中加深和巩固。

学以致用，举⼀反三

时下，最热门的莫过于人工智能，不过我们从事人工智能开发的同事常说⼈⼯智能其实就是⼈⼯智障，这么说并不过分，因为计算机真的很笨，它唯⼀能解决的问题就是穷举。对，你没有听错，它只能穷举所有可能性。

事实上，动态规划的思想就是从⼀系列算法中演进⽽来的。而贪⼼算法是求解整体最优的真正思路源头，因此有时候，我们需要考虑穷举的问题，最终通过优化形成了⼀个⽐较完美的总结，⽽这个总结正是动态规划的基本思想。

所以，我们可以看到，即便是⾼级的算法，如动态规划这样的思想也是通过不断的总结⽽得到的，因此算法基础就显得尤为重要。下面是学习动态规划需要掌握的知识的脑图，你可以通过这幅图对学习动态规划有⼀个全⾯的了解。

接下来，我将从动态规划的基本概念、基本特性，动态规划经典问题，动态规划的基本套路，动态规划优化和练习题等方面来介绍动态规划的相关内容。

何为动态规划

很多人对动态规划的概念或许还很模糊，那什么是动态规划呢？在正式回答这个问题之前，让我们先来看一下动态规划的产生背景。

动态规划是由 Dynamic Programming 翻译过来的。动态规划的概念是由美国数学R.E.Bellman等人提出的，主要应用于工程领域。动态规划是是求解多阶段决策过程(decision process)的最优化问题一种方法。

所谓多阶段决策过程，是指把一个复杂问题按时间(或空间)分成若干个阶段，每个阶段都需要作出决策，以便得到过程的最优结局。由于在每阶段采取的决策是与时间有关的而且前一阶段采取的决策如何，不但与该阶段的结果有关，还影响以后各阶段的结果，因此我们可以将这种多阶段决策问题看成是一个动态的问题，而处理的方法则被称为动态规划方法。事实上，动态规划也可以处理一些本来与时间没有关系的静态模型，这只要在静态模型中人为地引入“时间”因素，然后将这个静态模型使用时段进行拆分，就可以把它看作是多阶段的动态模型，用动态规划方法去处理。

简言之，多阶段决策过程指的是这样的一类特殊的活动过程：问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策组成一个决策序列。

为了方便大家理解多阶段决策过程，下面来看一个经典的最短选路算法。例如，在线路网络中，从A至E有一批货物需要调运，图上所标数字为各节点之间的运输距离，为使总运费最少，必须找出一条由A至E总里程最短的路线。

对于这类问题，我们首先需要对问题按照空间（时间）纬度进行拆分。对于上面的问题，我们可以将该问题拆分为A—B—C—D—E 4个阶段，然后在每个阶段都需要作出决策，即在A点需决策下一步到B1还是到B2或B3；同样，若到达第二阶段某个状态，比如B1 ，需决定走向C1还是C2 ，依次类推。可以看出：各个阶段的决策不同，由A至E的路线就不同，当从某个阶段的某个状态出发作出一个决策，则这个决策不仅影响到下一个阶段的距离，而且直接影响后面各阶段的行进线路。所以这类问题要求在各个阶段选择一个恰当的决策，使这些决策序列所决定的一条路线对应的总路程最短。

————————————————

原文链接：https://blog.csdn.net/xiangzhihong8/article/details/109102825

责任编辑：

标签：初始条件