动态规划

动态规划是什么

定义

动态规划（Dynamic programming，DP）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

简单来说，动态规划其实就是，给定一个问题，我们把它拆成一个个子问题，直到子问题可以直接解决。
然后呢，把子问题答案保存起来，以减少重复计算。再根据子问题答案反推，得出原问题解的一种方法。

一般这些子问题很相似，可以通过函数关系式递推出来，例如斐波那契数列，我们可以得到公式：当 n 大于 2的时候，F(n) = F(n-1) + F(n-2) ， f(10)= f(9)+f(8),f(9) = f(8) + f(7)...是重叠子问题，当n = 1、2的时候，对应的值为2，这时候就通过可以使用一个数组记录每一步计算的结果，以此类推，减少不必要的重复计算

若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。

通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：

一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。

这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

动态规划一般是比较高效，那么相对低效的是什么呢？暴力搜索！动态规划相对暴力搜索的优点在于去掉了重复的计算量，可以通过直接获取之前计算的结果来避免重复 计算，这是动态规划算法高效的重要原因。之前计算的结果都储存在表格中，也就是动态规划表。

动态规划与递归可以对应起来理解，前者是自底而上进行，后者是自顶而下进行搜索。同一个问题可能既可以用动态规划解决，也可以使用递归解决。

动态规划的核心代码量通常在几行到几十行，包含状态定义，状态初始化，状态转移方程三大主要部分。

动态规划是一种解决问题的思想

这种思想的本质是，一个规模比较大的问题， 是通过规模比较小的若干问题的结果来得到的（通过取最大，取最小，或者加起来之类的运算）。

动态规划常常适用于有重叠子问题和最优子结构性质的问题

基本思想:通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。 通常许多子问题非常相似，为此动态规划法试图仅仅解决每个 子问题1次，从而减少计算量： 一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。 这种做法在重复子问题的 数目关于输入的规模呈指数增长时特别有用。

分治法与动态规划 共同点 ：二者都要求原问题具有最优子结构性质,都是将原问题分而治之,分解成若干个规模较小(小到很容易解决的程序)的子问题. 然后将子问题的解合并,形成原问题的解.

不同点：分治法将分解后的子问题看成相互独立的，通过用递归来做。

动态规划将分解后的子问题理解为相互间有联系,有重叠部分，需要记忆，通常用迭代来做。

问题特征 最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。

重叠子问题：在用递归算法字顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质， 对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解

动态规划解决问题步骤

用动态规划解决问题时，要遵循三个重要步骤： (1) 定义子问题； (2) 实现要反复执行来解决子问题的部分（这一步要参考前一节讨论的递归的步骤）； (3) 识别并求解出基线条件。

如何判断一个问题可以使用动态规划来解决

发现一个问题适合用动态规划解决非常重要，能坚定信念去找状态转移方程！

需要满足两个重要的特点。存在最优子结构和重叠性

最优子结构：如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。（配题目来理解最优子结构）

重叠性：子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。（配图对比自顶而下和自下而上，及帮助理解重叠性）

根据题目要求的答案，1. 求最大值/最小值2. 求可不可行3. 求方案总数，就有较大概率使用动态规划。

适用场景

如果一个问题，可以把所有可能的答案穷举出来，并且穷举出来后，发现存在重叠子问题，就可以考虑使用动态规划 比如一些求最值的场景，如最长递增子序列、最小编辑距离、背包问题、凑零钱问题等等，都是动态规划的经典应用场景 关于动态规划题目解决的步骤，一般如下：

描述最优解的结构
递归定义最优解的值
按自底向上的方式计算最优解的值
由计算出的结果构造一个最优解

能用动态规划解决的一些著名问题

1.背包问题：给出一组项，各自有值和容量，目标是找出总值最大的项的集合。这个问题的限制是，总容量必须小于等于“背包”的容量。 2.最长公共子序列：找出一组序列的最长公共子序列（可由另一序列删除元素但不改变余下元素的顺序而得到）。 3.矩阵链相乘：给出一系列矩阵，目标是找到这些矩阵相乘的最高效办法（计算次数尽可能少）。相乘运算不会进行，解决方案是找到这些矩阵各自相乘的顺序。 4.硬币找零：给出面额为d1,...,dn 的一定数量的硬币和要找零的钱数，找出有多少种找零的方法。 5.图的全源最短路径：对所有顶点对(u,v)，找出从顶点U到顶点V的最短路径。

动态规划问题种类的判断正确（如判断出是某个经典问题或者是其变种），有助于快速分析出，状态的定义和状态转移方程。

动态规划问题的分类，一般可以按照问题中状态的定义来分的，一维，双一维，二维，区间，背包，划分型。

动态规划比较经典的问题种类有:

• 递推-斐波拉契数列，爬楼梯，

• 背包问题

• 最长递增子序列LIS

• 最长公共子序列LCS

• 最小路径和

• 最多路径数

动态规划的套路

套路是固定的，分为4个部分。1定义状态2推导状态转移方程3初始化状态4问题要求的最后答案是什么

（1）状态是什么，如何找到状态

首先判断状态是哪一种？一维，双一维，二维，区间，划分型。有两个难点。1是不容易看出来需要使用哪一种状态。2是不容易定义，前i个元素，还是以第i个元素结尾的序列等。较简单的比较容易能看得出来，有些题目不是那么容易看的出来的。一般而言，题目求什么，就定义状态是什么。如果不容易定义，可以根据属于哪一类经典问题，参考进行定义。

（2）如何找状态转移方程

可以使用数学证明中的归纳法！

F[n]的定义

动态规划的公式其实不难推，就那么几种（下面四种）。如果这几种套上去都搞不定，那么八成F[n]需要重新定义。

定义完毕，就要找F[n]和前面n步的关系了，分成四种，挨个套就行，难度由从低到高

a, F[n]跟前面一两步有关

这种简单

b, F[n]跟前面n步都有关

这种找到公式也不难，但要注意时间优化了，不优化往往就n^2了，举例子《最长上升子序列》，代码实现的过程中就需要借助for循环遍历前面所有的状态。

c, F[n]需要细分

这种情况下，你发现看着像，但是跟前面n步的关系整的你头疼。

举个例子，股票的几个中等难度的题就是这样。

那就把F[n]分成 F1[n] F2[n]，其实就是双一维类型

d, F[n]，一维数组不够用了

F[n]的细分其实是这个的简单情况。

举个例子，股票的状态有出售，买入。那么F[n]再加一维数组，变成 F[n][]，第二纬只有0，1即可。二维比较难的，二维里面还区分划分型。

对于二维的状态方程，使用dp表更加简洁明了，在对dp表进行初始化后，根据表格进行分析，更加容易找到规律。

在代码实现的过程中，i起始的取值从1还是2开始，取决于等式右边的索引不能为负，如果只有dp[i-1]，那可以从1开始；如果有dp[i-2]则只能从2开始。

如果当前状态与之前的所有状态都有关，就会有两层循环，内层循环要遍历之前的所有的状态

（3）如何进行初始化

对于一维，通常会是dp[0],dp[1]可能要初始化，初始化的目的是为了保证dp[i]的索引不出现负数。状态转移方程dp[i]=……，等式右侧中出现的如果只有dp[i-1]，则dp[0]初始化就行（索引i-1=0，i从1开始取），dp[1]可以推导出来；如果等式右侧出现了dp[i-2]，则需要初始化dp[0],dp[1]（索引i-2=0，i=2，最小可以推导的是dp[2]）。

对于二维，可能需要对dp[0][j]，和dp[i][0]，即第一行和第一列进行初始化。同样，如果出现了dp[i-2]的情况，也是需要对第二行和第二列进行初始化，不过一般都是只用初始化第一行和第一列。

在初始化的过程中，dp的长度也是个细节，有时与给定数组的长度相同，有时需要比给定数组的长度多一。这个是因为状态方程中出现了dp[i+1]，为了使数组索引时不越界，要使得其长度+1.

有的状态初始化其实在定义dp的时候就已经完成了初始化，没有专门的初始化代码。

从状态转移方程的下标思考初始化状态，注意数组的下标不能越界(上界和下界)，或者思考是否可以通过给状态数组多加样或一列，从而避免复杂的初始化讨论！

（4）问题的答案

如果状态的定义就是答案，通常就是dp[n]，如果不是就要根据具体的问题进行分析了，譬如有的是dp数组元素之和等等。