本文主要是介绍算法——动态规划(DP)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、例子

　　以状态转移方程入手很难理解动态规划本身，下面用几个例子说明什么是动态规划。

1、n个1累加

　　(1)1+1+1+1+1+1 = 6

　　(2)1+1+1+1+1+1+1 = ？

　　(3)1+1+1+1+1+1+1+1 = ？

　　　很快就能得出 (2)的结果是7，(3)的结果是8

　　　回忆得出结果的过程，我们并不是每次都从头到尾重新加，而是在已知 (1)的情况下，(2)的结果是 (1)的结果+1，同理 (3)是在 (2)的基础上+1。这就是最简单的动态规划，其特点如下：知道上一步骤的结果，把该结果交给当前步骤处理，得到的就是当前步骤的结果。

　　这里会产生一个问题，即规划的方向，比如(2)的结果是根据(1)的结果得到，假如我们不知道(1)，只知道最简单的“1 = 1”，则有以下两种做法

　　A.从后往前，把问题无限拆分，回到“最简单”的那一项。把(1)再分解为某一个式子+1，不断地拆+1 出来，一直拆到 1 = 1 为止.

　　B.从前往后，从“1 =1”开始，每一步 +1，直到满足要求。

2、斐波那契数列

　　斐波那契数列有如下定义：

　　f(0) = 0 

　　f(1) = 1 

　　f(n) = f(n-1) + f(n - 2)  ,  n>1

　　求第n项？

　　直观来想，假如我们想知道 f(10) ，那么我们就需要 f(9) 和 f(8) ，要知道 f(9) 则需要 f(8) 和  f(7) ，以此递归下去，最后一定会回到f(0) 和 f(1) 。这个特点与第一个例子中相同：知道上一步骤的结果，把该结果交给当前步骤处理，得到的就是当前步骤的结果。

　　但这个例子和第一个例子有很大不同，f(n) = f(n-1) + f(n - 2)  , 所以斐波那契数列需要的“上一步”，本质上是“上一步”和“上上步”。而这两步又有重合的地方，如果我们采取从后往前递归的方式写程序，则会计算大量的重复结点。正确做法是从前往后：从“最简单”的一项开始，每处理一步，就记录当前步骤结果，并设置为上一步，再据此找下一步的答案，直到满足要求，采用循环结构。这样每一个结点都只会被计算一次。

3、青蛙跳台阶

　　一只青蛙一次可以跳上1级 或 2级台阶，求跳上一个n级的台阶共有几种跳法？

　　类似例2，如果最终要跳上10级台阶，那么上一次跳完可能在第9级，也可能在第8级，以此类推。题目暗示了“最简单”的子问题是跳1级和跳2级。我们需要把这个“最简单”的子问题考虑清楚。跳1级只有1种跳法，而跳2级有2种，即跳2次1级或1次2级。之后用例2中说的方法即可求解。

二、动态规划

　1.要求：

• 知道上一步骤的结果，就能求出当前步骤的结果
• 不断追溯上一步，可以回到一个“最简单”的子问题，该子问题必须是已知的
• 每一步都基于同一种规则进行处理

　　2.处理步骤

1. 找“最简单”子问题，“最简单”子问题为开始递归时的第一个“上一步”
2. 循环结构，循环体中描述每一步共用的处理规则，之后储存当前步的结果，将其作为上一步
3. 循环结束，根据题目处理得到答案

　　3.特征

　　一般很难直接看出某个题是否可以用动态规划求解，但根据经验，能用动态规划的题一般符合以下特征：

1. 求统计类的问题，比如满足xx条件共有多少情况。也可能是求满足条件的某一项的问题。
2. 这个问题一般要完成一个复杂的大任务，但这个大任务可以分成若干步骤，且各步骤都有若干决策，每个步骤完成后，就到达了一个阶段性状态，可以据此完成下一步。
3. 题目可能会提示你：“答案可能会很大，请返回模 xxx 之后的结果”。动态规划每一步的结果是指数增长的，所以结果可能很大。关于取模：做题时有处理技巧： 先相加后取模 =  先取模后相加最后再取模  =  一个数取模一个数不取模,相加后再取模 。所以DP每一步记录取模后的结果即可，当然最后处理结果的时候别忘记取模。

三、一些比较复杂的DP问题

1.力扣2022.1.17每日一题 —— 1220.统计元音字母序列的数目

这篇关于算法——动态规划(DP)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！