当前位置：首页 > news >正文

「动态规划」1/n：什么是动态规划？

news 2024/10/31 7:06:36

动态规划这个名字听了一百遍，但是从来没有了解过，我连干嘛的都不清楚，但是如此高频率的出现，说明是有学习的必要的。

什么叫动态规划

在学习动态规划之前需要了解清楚什么叫做动态规划。很多教材直接讲内容了，并没有介绍其思想。

动态规划（Dynamic Programming，缩写 DP）是一种编程范式，并非一种具体的算法。动态规划就是把一个大问题通过递归的方法划分成多个小问题，用数学方式来表达的话，就是一个多项式。这样可以在代码量变化不大的情况下解决不同规模的问题（实现这点正是递归）。

这里多说一点：分而治之（Divide and Conquer，缩写 D&C）也是把一个大问题划分成小问题，但是分而治之是直接拆分的，而动态规划是递归拆分的，需要区分清楚二者。下面举两个例子来说明一下。

这里需要注意，动态规划并不是递归，它只是利用了递归。分而治之也可以使用递归，比如快速排序。

我们相加两个数组的时候，可以拆分成 n 对，然后 n 对一起相加。比如说每一对隔 x 个元素，比如一次计算a[1]+b[1]和a[10]+b[10]，第二次计算a[2]+b[2]和a[11]+b[11]，一直到计算完十个元素。这种拆分可能是连续的，也可能是随机的，但是这些拆分的部分之间没有任何关联性，比如a[1]与a[2]没有任何依赖关系。

但是动态规划的每个划分（或者说大多数划分）之间是要有关联，或者说依赖关系的。比如说提到动态规划入门必提的斐波那契数列。斐波那契数列的除了第一个元素（你也可以认为第二个元素是固定的，随你都行）之外，每个元素都是前两个元素相加得到的。所以斐波那契数列的表达式为：

$f ib (n) = f ib (n - 1) + f ib (n - 1)$

这样我们就可以通过迭代的到第 n 个斐波那契数列项的值，如下：

$1, 1, 2, 3, 5, 8, ......$

其实从这里你就会知道，为什么拓扑排序、关键路径这些东西为什么是动态规划里的，因为划分的时候，内容之间存在一定的关联性。而利用这些关联（也可以理解成一种限制），我们便可以找到一个最优解。所以动态规划通常用来求优化问题（optimization problem），你可以在力扣上看一下动态规划相关的题目，就会发现有很多题目中都有最短、最快、最高效这种优化关键词。

如何进行动态规划

一般进行动态规划的算法设计需要下面六个步骤：

子问题定义：确定子问题是什么，比如斐波那契数列的子问题就是 $fib(n)=fib_n$ 。
把子问题的解决方案与某些递归结构关联。比如计算斐波那契数列的某一项可以一直递归调用fib()函数，自然就得到最后的结果，也可以使用 for 循环（后者快一些）。
使用拓扑排序来确定这些子问题没有非循环的情况（这里需要你理解拓扑排序）。这话有点抽象，但其实你想想，递归子问题，或者说递归调用函数理解成一个图，不就是一个拓扑排序的过程吗？最开始入度为 0 的不就是第一个调用的子问题吗？而这个有向图一定可以得到一个没有回路的路径，也就是非循环的情况。如果有循环就永远不会结束了，说明这个算法有问题（曾经有个大佬的回忆录中就提到过学生时期刚学编程的时候，在学校的大型计算机上写了个循环的斐波那契算法，然后把机器搞坏的故事）。当然你可以可以使用其他算法来判断是否有循环的情况。
基本情况之间的关系。这其实是第 1、2 步之间的内容，例如 $f ib (n) = f ib (n - 1) + f ib (n - 1)$ 。
通过子问题来解决初始问题。
运行时间分析：斐波那契数列算法的复杂度是指数级的。