[算法思想]：动态规划_动态规划算法的根本思想是将待求解问题分解成若干子问题,先求解最小的子问题,

引入和介绍

  我们经常在别人讨论算法题目的时候，人们都会说到用动态规划来解决这个问题，所以动态规划是解决问题的一种思路，那么什么是动态规划呢？
 
  

什么是动态规划？

   所谓动态规划，是通过组合划分的子问题的解来求原问题的解。动态规划应用于子问题重叠的情况，既不同的子问题具有公共的子子问题（子问题的求解是递归进行的，然后将子问题话分为更小的子子问题，且子问题和子子问题具有共同的情况）
 

动态规划的应用场景，为什么要使用动态规划？

   动态规划方法一般用来求解最优解的问题。这一类的问题往往会有很多个可行解，每一个解都有一个值，然而我们希望找到具有最优值的解，我们称这样的解为问题的一个最优解，而不是最优解，因为肯有多个解都达到最优值。

动态规划核心思想：拆分子问题，记住过往，减少重复计算

说白了也就是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果。

最近有一个挺流行的例子来让我们来理解动态规划的核心思想：

A ： “1+1+1+1+1+1+1+1 =？”
A ： “上面等式的值是多少”
B ： 计算 “8”
A : 在上面等式的左边写上 “1+” 呢？
A : “此时等式的值为多少”
B : 很快得出答案 “9”
A : “你怎么这么快就知道答案了”
A : “只要在8的基础上加1就行了”
A : “所以你不用重新计算，因为你记住了第一个等式的值为8!动态规划算法也可以说是 ‘记住求过的解来节省时间’”
 

动态规划的具体步骤是怎么样的？

一般动态规划问题分为一下四个步骤：
1、穷举列出
2、确定边界
3、找出规律，得到最优子结构
4、写出状态转移方程

我们举个典型的例子来带你走进动态规划的问题 – 青蛙跳台阶的问题

牛客上的题：

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

数据范围：1≤n≤40
要求：时间复杂度：O(n)O(n) ，
空间复杂度： O(1)O(1)

解这个题目有两种方法：
一种是用递归来解决，另一种是用动态规划来解决，由于递归会损耗较大的系统资源，会存在大量的重复计算，性能非常低下（其实我们这里也可以提升递归性能，就是可以先把计算好的答案存下来，即造一个备忘录，等到下次需要的话，先去备忘录查一下，如果有，就直接取就好了，备忘录没有才开始计算，那就可以省去重新重复计算的耗时，一般使用一个数组或者一个哈希map充当这个备忘录），故我们这里使用动态规划来解决。

动态规划跟带备忘录的递归解法基本思想是一致的，都是减少重复计算，时间复杂度也都是差不多。但是呢：
1、带备忘录的递归，是从f(10)往f(1）方向延伸求解的，所以也称为自顶向下的解法。
2、动态规划从较小问题的解，由交叠性质，逐步决策出较大问题的解，它是从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)就是重叠子问题。
我们来看下自底向上的解法，从f(1)往f(10）方向

仔细观察上图，可以发现，f（n）只依赖前面两个数，所以只需要两个变量a和b来存储，就可以满足需求了

过程：
1、穷举列出
当台阶数是1的时候，有一种跳法，f（1） =1
当只有2级台阶时，有两种跳法，第一种是直接跳两级，第二种是先跳一级，然后再跳一级。即f(2) = 2;
当台阶是3级时，想跳到第3级台阶，要么是先跳到第2级，然后再跳1级台阶上去，要么是先跳到第 1级，然后一次迈 2 级台阶上去。所以f(3) = f(2) + f(1) =3，跳到f(3)前需要有跳到f(2)和f(1)两种
当台阶为4级时，同理f(4) = f(3) + f(2)
…

2、确定边界
显然f(1) = 1; f(2) = 2；这里就不多说了

3、找出规律，得到最优子结构
n>=3时，已经呈现出规律 f(n) = f(n-1) + f(n-2) ，因此，f(n-1)和f(n-2) 称为 f(n) 的最优子结构

4、写出状态转移方程：
f(n) = f(n-1) + f(n-2) ,n>=3;

综上所述，写出对应的算法即可
 

代码

    public int jumpFloor(int target) {
        int target1 = 1;
        int target2 = 2;
        int result = 0;
        if (target == 1) {
            return 1;
        }
        if (target == 2) {
            return 2;
        }
        for (int i = 3; i <= target; i++) {
            result = target1 + target2;
            target1 = target2;
            target2 = result;

        }
        return result;

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19