[数据结构与算法]【算法】动态规划

系列文章目录

【算法】动态规划
动态规划算法Oj题（一）
动态规划算法Oj题（二）
动态规划算法Oj题（三）

0. 前言

本节内容是动态规划算法系列之一：动态规划的介绍，主要介绍了动态规划的定义，什么样的问题适合用动态规划算法去求解，最后说明动态规划算法在日常生活中的应用场景。

1. 动态规划的概念

动态规划（英语：Dynamic programming，简称 DP），是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。

上述说法看起来似乎很抽象，换个说法就是：
动态规划是分治思想的延伸，通俗一点来说就是大事化小，小事化无的艺术。在将大问题化解为小问题的分治过程中，保存对这些小问题已经处理好的结果，并供后面处理更大规模的问题时直接使用这些结果。

2. 动态规划思想及特点

2.1 动态规划思想

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。

2.2 动态规划的特点

动态规划具备了以下三个特点:

1. 把原来的问题分解成了几个相似的子问题。
2. 所有的子问题都只需要解决一次。
3. 储存子问题的解。

动态规划算法更多的时候是用来求解一些最优化问题，这些问题有很多可行解，每个解都有一个值，利用动态规划算法是希望找到具有最优值的解。接下来，就让我们具体看看动态规划算法的求解思路及相关应用场景。

3. 动态规划算法求解分析

3.1 适用问题

首先，在利用动态规划算法之前，我们需要清楚哪些问题适合用动态规划算法求解。一般而言，能够利用动态规划算法求解的问题都会具备以下两点性质：

1. 最优子结构

利用动态规划算法求解问题的第一步就是需要刻画问题最优解的结构，并且如果一个问题的最优解包含其子问题的最优解，则此问题具备最优子结构的性质。因此，判断某个问题是否适合用动态规划算法，需要判断该问题是否具有最优子结构。

最优子结构的定义主要是在于当前问题的最优解可以从子问题的最优解得出，当子问题满足最优解之后，才可以通过子问题的最优解获得原问题的最优解。

2. 重叠子问题

适合用动态规划算法去求解的最优化问题应该具备的第二个性质是问题的子问题空间必须足够” 小 “，也就是说原问题递归求解时会重复相同的子问题，而不是一直生成新的子问题。如果原问题的递归算法反复求解相同的子问题，我们就称该最优化问题具有重叠子问题。

在这里，我们需要注意是，与适用动态规划算法去求解的问题具备重叠子问题性质相反，前面我们介绍的分治算法递归解决问题时，问题的子问题都是互不影响，相互独立的，这个也是我们在选用动态规划算法还是分治法解决问题时的一个判断条件。

3.2 算法步骤

在明确什么样的问题适合用动态规划算法去求解时，我们需要掌握动态规划算法的求解步骤：

步骤 1： 刻画一个最优解的结构特征

适合用动态规划算法求解的问题需要满足最优子结构的特征，所以在应用动态规划算法时的第一步就是刻画问题最优解的结构，一般都是用一些数学方法去描述求解问题，用数学公式表明最优解的结构特征。

步骤 2： 递归的定义最优解的值

当应用动态规划算法求解问题时，一般我们会递归的求解相同的子问题，这个时候，我们就需要去递归的定义最优解的值，通常也是先用数学公式去递归定义。

步骤 3： 计算最优解的值

当我们可以清楚的刻画一个最优解的结构特征及可以递归的定义出最优解的值之和，一般我们就可以采用自底向上的方法逐步去计算每一个最优解的值，大问题的最优解的值依赖于小问题的最优解的值，这个是动态规划算法的核心思想。

步骤 4: 利用计算出的信息构造一个最优解

前面的步骤 1,2,3 是动态规划算法求解问题的基础，如果我们仅仅需要一个最优解的值，而不是需要了解最优解本身，我们可以不用去执行步骤 4；如果我们需要了解最优解的具体情况，我们就需要在执行步骤 3 的时候维护一些额外的信息，以便用来构造出一个最优解。

4. 动态规划的应用场景

动态规划示例问题：爬楼梯

假设你现在正在爬楼梯，一共需要经过 n 阶楼梯你才可以到达楼顶。每次你可以爬 楼梯的 1 或 2 个台阶。请问一共有多少种不同的方法可以爬到楼顶？

现在，让我们按照动态规划算法的求解步骤我们来分析一下这个问题：

步骤 1： 刻画爬楼梯问题一个最优解的结构特征

情况 1：输入 n=1；输出为 1
解释 1：有一种情况可以爬上楼顶， 爬 1 步，记为 1

情况 2：输入 n=2；输出为 2
解释 2：有两种情况可以爬上楼顶，分别为连续两次爬一阶楼梯和一次爬两阶楼梯，记为 1+1，2

情况 3：输入 n=3；输出为 3
解释 3：有三种情况可以爬上楼顶，如情况 1 和 2 描述一样，记为 1+1+1,2+1,1+2

通过分析可以知道，爬楼梯问题主要在于我们可以一次爬两步或者一步，所以到达最后一阶楼梯 n 时，我们可以从第 n-2 阶楼梯爬两步或者第 n-1 楼梯爬一步完成。
当我们需要知道最多有多少种方法可以爬上 n 阶的楼梯时，我们需要分别知道爬上第 n-2 阶楼梯最多有多少种方法，爬上第 n-1 阶楼梯最多有多少种方法，然后爬上第 n 阶楼梯的最多方法数量等于爬上第 n-1 阶楼梯最多的方法数量加上爬上第 n-2 阶楼梯最多的方法数量。

步骤 2： 递归的定义爬 n 阶楼梯最多的方法数

• 上 1 阶台阶：有 1 钟方法；
• 上 2 阶台阶：有 1+1 和 2 两种方法；
• 上 3 阶台阶：到达第 3 阶的方法总数是到达第 1 阶和第 2 阶方法的总和；
• 上 n 阶台阶：到达第 n 阶的方法总数就是到第 (n-1) 阶和第 (n-2) 阶的方法数之和。

综上所述，我们可以知道爬 n 阶楼梯的状态转移方程可以定义为：goStep (n) = goStep (n-1)+goStep (n-2)。动态规划算法最重要的就是去定义这个状态转移方程，通过这个状态转移方程我们就可以很清楚的去计算。

步骤 3： 计算爬 n 阶楼梯最多方法数的值

步骤 4： 利用计算出的信息构爬 n 阶楼梯每次走几步的方法

其实在爬楼梯这个问题中，我们并不需要统计每次的具体爬楼梯方法，如果需要统计每次具体走法时，需要在计算的时候记录之前的每一步走法，把信息全部记录保留下来即可。

总结

本节主要介绍了动态规划算法的定义及基本概念，想要掌握动态规划，需要明白什么样的问题适合利用动态规划求解，如何自己去设计一个动态规划算法，以及我们日常生活中哪些应用场景适合用动态规划思想解决问题。