%%参考：https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie/1.1-dong-tai-gui-hua-ji-ben-ji-qiao/dong-tai-gui-hua-xiang-jie-jin-jie
首先，动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多，比如说让你求最长递增子序列呀，最小编辑距离呀等等。
既然是要求最值，核心问题是什么呢？求解动态规划的核心问题是**穷举。因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值呗。
首先，动态规划的穷举有点特别，因为这类问题存在「重叠子问题」**，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。

动态规划的总结与思考 - 图1
而且，动态规划问题一定会具备「**最优子结构**」，才能通过子问题的最值得到原问题的最值。

题解套路

第一步：要明确 dp 数组的含义。如在最长子序列中，dp表示i的前缀序列中的最长子序列长度。
第二步：定义 base case。即初始化，dp[0][…]=0等等。
第三步，找状态转移方程。即dp[i-1]与dp[i]之间的递推关系。

动态规划的前身与由来

以斐波那契数列的求解为例：

  1. 暴力求解

斐波那契数列的数学形式就是递归的，写成代码就是这样：

  1. public int Feb(int N){
  2.     if(N==0)
  3.         return 0;
  4.     if(N==1)
  5.         return 1;
  6.     return Feb(N-2)+F(N-1);
  7. }
  1.    这个不用多说了，学校老师讲递归的时候似乎都是拿这个举例。我们也知道这样写代码虽然简洁易懂，但是十分低效, 重复计算量非常大。

  1. 一点点改进：备忘录算法

    1. 明确了问题，其实就已经把问题解决了一半。即然耗时的原因是重复计算，那么我们可以造一个「备忘录」，每次算出某个子问题的答案后别急着返回，先记到「备忘录」里再返回；每次遇到一个子问题先去「备忘录」里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了。<br />     一般使用一个数组充当这个「备忘录」，当然你也可以使用哈希表（字典），思想都是一样的。
    1. public int fib(int N){
    2.  int[] memo = new int[N+1,0]
    3.  return helper(memo, N);
    4. }
    5. private int helper(int[] memo, int N){
    6.  if(N==0)
    7.      return 0;
    8.  if(N==1)
    9.      return 1;
    10.  if(memo[N]!=0)
    11.      return memo[N]
    12.  else return helper(memo, N - 1) + helper(memo, N - 2);
    13. }

    实际上，带「备忘录」的递归算法，把一棵存在巨量冗余的递归树通过「剪枝」，改造成了一幅不存在冗余的递归图，极大减少了子问题（即递归图中节点）的个数。
    至此，带备忘录的递归解法的效率已经和迭代的动态规划解法一样了。实际上，这种解法和迭代的动态规划已经差不多了，只不过这种方法叫做「自顶向下」，动态规划叫做「自底向上」。

  2. 自底向上的动态规划算法

有了上一步「备忘录」的启发，我们可以把这个「备忘录」独立出来成为一张表，就叫做 DP table 吧，在这张表上完成「自底向上」的推算岂不美哉！

  1. public int fib(int N){
  2.     int[] dp= new int[N+1];
  3.     dp[0]=0;
  4.     dp[1]=1;
  5.     for(int i=2; i<=N; i++){
  6.         dp[i]=dp[i-1]+dp[i-2];
  7.     }
  8.     return dp[N];
  9. }