算法设计 - 动态规划（一）初识

深碍√TFBOYSˉ_ 2023-09-26 09:54 15阅读 0赞

**目录**

动态规划

概念

基本思想

--------------------

## 动态规划 ##

### 概念 ###

动态规划，英文是Dynamic Programming，简称DP。其中：

*  “动态”指的是：在一定条件下，当前阶段的状态和下一阶段的状态之间的转移。
 *  “规划”指的是：建立状态转移方程，将各个阶段的状态以表格式方法存储。（PS：表格式方法：用一个表来记录已解决的子问题的解）

动态规划有四个关键术语：

*  阶段（stage）：将所给的问题，按时间或空间特征分解成若干个有联系的阶段，以便按次序去求解每阶段的解。
 *  状态（state）：各阶段开始时的客观条件叫做状态
 *  决策（decision）：当各阶段的状态确定以后，就可以做出不同的决定，从而确定下一阶段的状态，这种决定称为决策。
 *  转移（transition）：根据上一阶段的状态和决策来导出本阶段的状态。

### 基本思想 ###

动态规划的基本思想是：将原问题分解为若干个子问题。

这点和分治法类似，分治法也是将原问题分解为若干个子问题。

例如，经典的fibnaci数列，就经常用分治法求解：

比如将求解第n个fibnaci数，分治为求解第n-1个，和第n-2个fibnaci数，然后以此递归下去，直到求解第0个和第1个fibnaci数。

function fibnaci(n) {
      if (n < 2) return n;
      return fibnaci(n - 1) + fibnaci(n - 2);
    }

但是当n值比较大时，上述分治法求解就会非常吃力，这是因为，分治法在原问题分解过程中会产生非常多的重叠子问题，如下图所示，f(6)的求解过程中，f(4)、f(3)、f(2)、f(1)、f(0) 会被重复求解多次，这是非常浪费时间的

![fd1976fea3074977a7445a1e64933fe3.png][]

我们期望的是，如果某个fibnaci数求解后则记录下来，当下次再求解这个fibnaci数时，不再重新求解，而是去记录中获取。

let cache = [0, 1];
    
    function fibnaci(n) {
      if (cache[n] !== undefined) return cache[n];
      cache[n] = fibnaci(n - 1) + fibnaci(n - 2);
      return cache[n];
    }

此时，fibnaci数的求解被大大简化，很多重复子问题求解被剪枝

![38716fac05be4052847401dcd5183c55.png][]

但是带记录的分治法任然存在重复子问题求解，如下图中的f(1)、f(2)、f(3)、f(4)

![9093bb9d45bf49edacf9957597a3bcf2.png][]

这是由于递归必然依赖于函数调用。

分治法是将原问题分解为了若干个子问题，然后求出子问题的解，再将所有子问题的解合并为原问题的解。但是在问题分解过程中，可能会产生重叠子问题，导致分治法效率降低。

下面我们通过动态规划来解决上述问题：

function fibnaci(n) {
      let dp = new Array(n);
    
      dp[0] = 0;
      dp[1] = 1;
    
      for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
      }
    
      return dp[n];
    }

从上面代码逻辑，我们可以分析出：

dp\[0\] = 0

dp\[1\] = 1

dp\[2\] = dp\[1\] + dp\[0\]

dp\[3\] = dp\[2\] + dp\[1\]

dp\[4\] = dp\[3\] + dp\[2\]

.....

dp\[n\] = dp\[n-1\] + dp\[n-2\]

这是一个bottom-up自底向上递推求解原问题的过程，在这个过程中不会发生子问题的重复求解。

其中dp数组就是动态规划中记录子问题解的表，dp\[n\] = dp\[n-1\] + dp\[n-2\]就是状态转移方程，除了dp\[0\]、dp\[1\]外的其他阶段的状态求解都依赖于前面阶段的状态。

因此，动态规划和分治法最大的区别在于：

1.  动态规划采用的是递推bottom-up，分治法采用的是递归top-down
2.  动态规划天生就需要记录子问题的解，而分治法可以选择不记录子问题的解
3.  动态规划不存在子问题重复求解现象，而分治法可能会存在重叠子问题

动态规划的使用场景和分治法很像，但是也有明显差别：

1.  原问题的规模缩小到一定程度就可以容易地解决。比如fibnaci(0)、fibnaci(1)的求解
2.  原问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。比如fibnaci(n) = fibnaci(n-1) + fibnaci(n-2); n>1，其中fibnaci(n)是原问题，fibnaci(n-1)、fibnaci(n-2)是规模更小的相同问题。
3.  利用原问题分解出来的子问题的解可以合并为原问题的解。这个条件是采用分治法解决问题的根本条件。如果不具备该条件则需要考虑动态规划。
4.  原问题分解出来的子问题是相互独立的，即不存在重叠子问题。这个条件是分治法高效解决问题的必要条件，如果不满足此条件，则分治法解决问题的效率会大大折扣，此时应该考虑动态规划。

[fd1976fea3074977a7445a1e64933fe3.png]: https://img-blog.csdnimg.cn/fd1976fea3074977a7445a1e64933fe3.png
[38716fac05be4052847401dcd5183c55.png]: https://img-blog.csdnimg.cn/38716fac05be4052847401dcd5183c55.png
[9093bb9d45bf49edacf9957597a3bcf2.png]: https://img-blog.csdnimg.cn/9093bb9d45bf49edacf9957597a3bcf2.png