0.前言

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

动态规划可以从下面的参考网上的一个例子：

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

1.动态规划的两种基本形式

一般求解的方式有两种：①自顶向下的备忘录法 ②自低向上

为了说明动态规划的这两种方法，举个简单例子：
【题目描述】已知斐波那契数列第n项。0，1，1，2，3，5，8.......输出斐波那契数列的第n项。

【输入描述】一个正整数n。表示第n项。

【输出描述】第n项是多少。

【样例输入】4

【样例输出】2

我们前面解过这个题目，很快可以写出递归函数来。

nt calculate(int n) 
{
    if(n==1)    return 0;//判断是否到达递归边界n=1
    else if(n==2)   return 1;//判断是否到达递归边界n=2
    else    return calculate(n-1)+calculate(n-2);//未到达继续递归
}

我们分析一下递归的流程，加入计算n=5

[图片=http:??]

上面的递归树中的每一个子节点都会执行一次，很多重复的节点被执行，calculate(2)被重复执行了3次。由于调用每一个函数的时候都要保留上下文，所以空间上开销也不小。这么多的子节点被重复执行，如果在执行的时候把执行过的子节点保存起来，后面要用到的时候直接查表调用的话可以节约大量的时间。

下面看看动态规划如何求解斐波那契数列问题？

①自顶向下——备忘录法

参考代码：

public class Solution {
//使用哈希map，充当备忘录的作用
		Map<Integer, Integer> tempMap = new HashMap();
		public int numWays(int n) {
// n = 0 也算1种
			if (n == 0) {
				return 1;
			}
			if (n <= 2) {
				return n;
			}
//先判断有没计算过，即看看备忘录有没有
			if (tempMap.containsKey(n)) {
//备忘录有，即计算过，直接返回
				return tempMap.get(n);
			} else {
// 备忘录没有，即没有计算过，执行递归计算,并且把结果保存到备忘录map中，对1000000007取余（这个是leetcode题目规定的）
				tempMap.put(n, (numWays(n - 1) + numWays(n - 2)) % 1000000007);
				return tempMap.get(n);
			}
		}
}

备忘录法也是比较好理解的，创建了一个n+1大小的数组来保存求出的斐波拉契数列中的每一个值，在递归的时候如果发现前面fib（n）的值计算出来了就不再计算，如果未计算出来，则计算出来后保存在数组中，下次在调用fib（n）的时候就不会重新递归了。比如上面的递归树中在计算fib（6）的时候先计算fib（5），调用fib（5）算出了fib（4）后，fib（6）再调用fib（4）就不会在递归fib（4）的子树了，因为fib（4）的值已经保存在其中了。

②自底向上的动态规划

备忘录法还是利用了递归，上面算法不管怎样，计算fib（6）的时候最后还是要计算出fib（1），fib（2），fib（3）…,那么何不先计算出fib（1），fib（2），fib（3）…,呢？这也就是动态规划的核心，先计算子问题，再由子问题计算父问题。

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

• 带备忘录的递归，是从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)就是重叠子问题。

我们来看下自底向上的解法，从f(1)往f(10）方向，想想是不是直接一个for循环就可以解决啦，如下：

int fibonacciDP2(int n) {       // 动态规划使用数组
    int *a = new int[n+1];
    
    a[0] = 0, a[1] = 1;
    for (int i = 2; i < n+1; i++) {
        a[i] = a[i - 1] + a[i - 2];
    }
    return a[n];}

动态规划的解题套路

什么样的问题可以考虑使用动态规划解决呢？

如果一个问题，可以把所有可能的答案穷举出来，并且穷举出来后，发现存在重叠子问题，就可以考虑使用动态规划。

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

动态规划的解题思路

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

• 穷举分析

• 确定边界

• 找出规律，确定最优子结构

• 写出状态转移方程

简单模板：

dp[0][0][...] = 边界值
for(状态1 ：所有状态1的值){
    for(状态2 ：所有状态2的值){
        for(...){
          //状态转移方程
          dp[状态1][状态2][...] = 求最值
        }
    }
}