一、概念

动态规划（Dynamic programming，简称 DP），是通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
换句话说，就是给定一个问题，我们把它拆成一个个子问题，直到子问题可以直接解决。然后呢，把子问题答案保存起来，以减少重复计算。再根据子问题答案反推，得出原问题解的一种方法。
动态规划常常适用于有重叠子问题和最优子结构性质的问题。

二、核心思想

动态规划最核心的思想，就在于拆分子问题，记住过往，减少重复计算。
来看一道经典DP问题『青蛙跳台阶』，从这道题就能体会到DP的思想。

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

可以这么理解，假设跳到第n级台阶的跳数我们定义为。
要跳到第10级台阶，要么是先跳到第9级，然后再跳1级台阶上去；要么是先跳到第8级，然后一次迈2级台阶上去。所以。
同理，要跳到第9级台阶，要么是先跳到第8级，然后再跳1级台阶上去；要么是先跳到第7级，然后一次迈2级台阶上去。所以。
依次类推到最后，。至于，要么直接跳两级，要么一级一级跳，所以；而只有一种跳法。
看到这里，是不是可以用递归解决，因为，代码如下

class Solution {
 public:
  int numWays(int n) {
    if (n <= 2) {
      return n;
    }
    return numWays(n - 1) + numWays(n - 2);
  }
};

有没有发现，这其实就是个斐波那契，所以用递归计算时间复杂度是（具体时间复杂度计算可以看我另一篇文章）
回过头来，你仔细观察这颗递归树，你会发现存在大量重复计算，比如和，这里被计算了两次。所以这个递归算法低效的原因，就是存在大量的重复计算！
既然存在大量重复计算，那么我们可以先把计算好的答案存下来，等到下次需要的话，先去记录里查一下，有就直接取，没有再计算，就可以省去重新重复计算的耗时。一般使用一个数组或者一个哈希充当这个备忘录。
解法如下（很可惜，超时了）：

class Solution {
 public:
  int numWays(int n) {
    unordered_map<int, int> tempMap;
    // n = 0 也算1种
    if (n == 0) {
      return 1;
    }
    if (n <= 2) {
      return n;
    }
    // 先判断有没计算过,即看看备忘录有没有
    if (tempMap.find(n) != tempMap.end()) {
      // 备忘录有,即计算过,直接返回
      return tempMap[n];
    } else {
      // 备忘录没有,即没有计算过,执行递归计算,并且把结果保存到备忘录map中,对1000000007取余(这个是leetcode题目规定的)
      tempMap.insert(pair<int, int>(n, (numWays(n - 1) + numWays(n - 2)) % 1000000007));
      return tempMap[n];
    }
  }
};

那这种解法跟动态规划有啥关系呢？动态规划跟带备忘录的递归解法基本思想是一致的，都是减少重复计算，时间复杂度也都是差不多。但是有两点不一样：

带备忘录的递归，是从往方向延伸求解的，所以也称为自顶向下的解法
动态规划从较小问题的解，由交叠性质，逐步决策出较大问题的解，它是从往方向，往上推求解，所以称为自底向上的解法

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

和称为的最优子结构
就称为状态转移方程
，就是边界
比如和中，就是重叠子问题

代码如下：

class Solution {
 public:
  int numWays(int n) {
    if (n == 0) {
      return 1;
    }
    if (n <= 2) {
      return n;
    }
    int dp[n + 1];
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i < n + 1; i++) {
      dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
    }
    return dp[n];
  }
};

三、解题思路

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

穷举分析
确定边界
找出规律，确定最优子结构
写出状态转移方程

穷举分析

当台阶数是1的时候，有一种跳法，
当只有2级台阶时，有两种跳法，第一种是直接跳两级，第二种是先跳一级，然后再跳一级。即;
当台阶是3级时，想跳到第3级台阶，要么是先跳到第2级，然后再跳1级台阶上去，要么是先跳到第 1级，然后一次迈 2 级台阶上去。所以
当台阶是4级时，依次类推

确定边界

通过穷举分析，我们发现，当台阶数是1的时候或者2的时候，可以明确知道青蛙跳法。，当台阶时，已经呈现出规律，因此就是青蛙跳阶的边界。

找规律，确定最优子结构

时，已经呈现出规律，因此，和称为的最优子结构。
什么是最优子结构？有这么一个解释

一道动态规划问题，其实就是一个递推问题。假设当前决策结果是，则最优子结构就是要让最优，最优子结构性质就是能让转移到n的状态是最优的，并且与后面的决策没有关系，即让后面的决策安心地使用前面的局部最优解的一种性质。

写出状态转移方程

通过前面3步，穷举分析，确定边界，最优子结构，我们就可以得出状态转移方程：
$$ f(n)=\left{

\right.
$$

代码实现

实现代码的时候，一般注意从底往上遍历，然后关注下边界情况，空间复杂度。动态规划有个大概框架

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

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。

请作者喝杯咖啡吧