hello大家好 我是大家的学习成长小伙伴Captain

动态规划，大家肯定都听过这个名词，这个是很经典的一个解决问题的思路，也是很有技巧的，一般大厂也喜欢问这种类型的问题

今天我们一起来学习一下动态规划到底是个什么

什么是动态规划？

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

动态规划常常适用于有重叠子问题[1]和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。

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

核心思想

动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。

动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。

在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

按照定义来看，动态规划就是把一个大问题然后拆分成很多小问题，这个本身是没啥问题的，其实啊，我个人觉得这不是动态规划的核心思想

事实上是任何大问题都能拆解成许多小问题，一个大问题之所以能用动态规划来解决，并不是因为它可以拆解成很多小问题，这不是关键

动态规划的本质不在于是递推或是递归，也不需要纠结是不是内存换时间，本质是解决的这些小问题是否能够被重复调用，这就是问题是否可以用动态规划解决的要素

我们先来看一个最熟悉的例子

斐波那契数列（Fibonacci polynomial）

计算斐波那契数列（Fibonacci polynomial）的一个最基础的算法是，直接按照定义计算（函数递归）：

   function fib(n）       if n = 0 or n = 1           return n       return fib(n − 1) + fib（n − 2）

当n=5时，fib(5)的计算过程如下:

fib(5)fib(4) + fib(3)(fib(3) + fib(2)) + (fib(2) + fib(1))((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

由上面可以看出，这种算法对于相似的子问题进行了重复的计算，因此不是一种高效的算法。实际上，该算法的运算时间是指数级增长的。

我们可以通过保存已经计算过的子问题的解来避免重复计算

再来看一个类似的例子，青蛙跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 10 级的台阶总共有多少种跳法。

其实这个问题思路也是比较简单的，要想跳到第10级台阶，要么是先跳到第9级，然后再跳1级台阶上去;要么是先跳到第8级，然后一次迈2级台阶上去。

同理，要想跳到第9级台阶，要么是先跳到第8级，然后再跳1级台阶上去;要么是先跳到第7级，然后一次迈2级台阶上去。

要想跳到第8级台阶，要么是先跳到第7级，然后再跳1级台阶上去;要么是先跳到第6级，然后一次迈2级台阶上去。

假设跳到第n级台阶的跳数我们定义为f(n)，可以得出公式：

f（10） = f（9）+f(8)f (9)  = f(8) + f(7)f (8)  = f(7) + f(6)...f(3) = f(2) + f(1)
即通用公式为: f(n) = f(n-1) + f(n-2)

那f(2) 或者 f(1) 等于多少呢？

当只有2级台阶时，有两种跳法，第一种是直接跳两级，第二种是先跳一级，然后再跳一级。即f(2) = 2;

当只有1级台阶时，只有一种跳法，即f（1）= 1；

public int getNum(int n) {  if(n == 1){      return 1;   }   if(n == 2){      return 2;   }  return getNum(n-1) + getNum(n-2);}

大家通过看上面两个例子心中是怎么想的呢

聪明的你们应该早已经发现其中的相似点了，没错，它们的共同点就是都是有一些子问题作为根基，然后这些子问题会被重复的调用，计算

要计算最大的值，就必须先计算子问题，要计算子问题，就必须计算更子的问题

仔细想一下这个计算过程，太多太多的重复计算了，每一个都被计算了不止一次，尤其是f(1)这种，所以这种是很低效的

既然存在了大量的重复计算，我们就可以先把计算好的答案保存下来，其实也就是一个备忘录，等到下次需要的话，也就是先去备忘录查询一下，如果有，就直接取备忘录的值就可以了，备忘录没有才开始计算

类似于我们平时系统中的缓存的效果

动态规划跟带备忘录的递归解法基本思想是一致的，都是减少重复计算，时间复杂度也都是差不多。

但是呢

带备忘录的递归，是从f(10)往f(1）方向延伸求解的，所以也称为自顶向下的解法。

动态规划从较小问题的解，由交叠性质，逐步决策出较大问题的解，它是从f(1)往f(10）方向，往上推求解，所以称为自底向上的解法。

动态规划有几个典型特征，最优子结构、状态转移方程、边界、重叠子问题。

在青蛙跳阶问题中：

f(n-1)和f(n-2) 称为 f(n) 的最优子结构

f(n)= f（n-1）+f（n-2）就称为状态转移方程

f(1) = 1, f(2) = 2 就是边界啦

比如f(10)= f(9)+f(8),f(9) = f(8) + f(7) ,f(8)就是重叠子问题。

动态规划中的解题套路

通过上面说了这么多了，我们知道动态规划的关键在于：存在重叠子问题！

动态规划的本质不在于是递推或是递归，也不需要纠结是不是内存换时间，本质是解决的这些小问题是否能够被重复调用，这就是问题是否可以用动态规划解决的要素

• 将原问题分解为子问题
• 确定状态
• 确定一些初始状态（边界状态）的值
  
• 写出状态转移方程

如果一个大问题，可以把所有可能的答案都穷举出来，穷举出来之后会发现有很多重叠的子问题，就可以考虑使用动态规划

比如一些求最值的场景，如最长递增子序列、最小编辑距离、背包问题、凑零钱问题等等，都是动态规划的经典应用场景。

动态规划的核心思想就是拆分子问题，记住过往，减少重复计算。并且动态规划一般都是自底向上的，因此到这里，基于青蛙跳阶问题，我总结了一下我做动态规划的思路：

1、将原问题分解为子问题

把原问题分解为若干个子问题，子问题和原问题形式相同 或类似，只不过规模变小了。

子问题都解决，原问题即解 决(数字三角形例）。l 子问题的解一旦求出就会被保存，所以每个子问题只需求 解一次。 

2、确定状态

在用动态规划解题时，我们往往将和子问题相 关的各个变量的一组取值，称之为一个“状态”。

一个“状态”对应于一个或多个子问题， 所谓某个“状态”下的“值”，就是这个“状 态”所对应的子问题的解。

所有“状态”的集合，构成问题的“状态空间”。“状态 空间”的大小，与用动态规划解决问题的时间复杂度直接相关。在数字三角形的例子里，一共有N×(N+1)/2个数字，所以这个 问题的状态空间里一共就有N×(N+1)/2个状态。

整个问题的时间复杂度是状态数目乘以计算每个状态所需时间。            

在数字三角形里每个“状态”只需要经过一次，且在每个 状态上作计算所花的时间都是和N无关的常数。  

用动态规划解题，经常碰到的情况是，K个整型变量能 构成一个状态（如数字三角形中的行号和列号这两个变量 构成“状态”）。如果这K个整型变量的取值范围分别是 N1, N2, ……Nk，那么，我们就可以用一个K维的数组 array[N1] [N2]……[Nk]来存储各个状态的“值”。

这个 “值”未必就是一个整数或浮点数，可能是需要一个结构 才能表示的，那么array就可以是一个结构数组。一个 “状态”下的“值”通常会是一个或多个子问题的解。

3、确定一些初始状态（边界状态）的值

以“数字三角形”为例，初始状态就是底边数字，值 就是底边数字值。

4、确定状态转移方程

定义出什么是“状态”，以及在该 “状态”下的“值”后，就要 找出不同的状态之间如何迁移――即如何从一个或多个“值”已知的 “状态”，求出另一个“状态”的“值”(“人人为我”递推型)。

状态的迁移可以用递推公式表示，此递推公式也可被称作“状态转移方程”。

能用动规解决的问题的特点

1) 问题具有最优子结构性质。

如果问题的最优解所包含的 子问题的解也是最优的，我们就称该问题具有最优子结 构性质。

2) 无后效性。

当前的若干个状态值一旦确定，则此后过程 的演变就只和这若干个状态的值有关，和之前是采取哪 种手段或经过哪条路径演变到当前的这若干个状态，没有关系。