什么是动态规划

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

dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.

以上定义来自维基百科，看定义感觉还是有点抽象。简单来说，动态规划其实就是，给定一个问题，我们把它拆成一个个子问题，直到子问题可以直接解决。然后呢，把子问题答案保存起来，以减少重复计算。再根据子问题答案反推，得出原问题解的一种方法。

一般这些子问题很相似，可以通过函数关系式递推出来。然后呢，动态规划就致力于解决每个子问题一次，减少重复计算,比如斐波那契数列就可以看做入门级的经典动态规划问题。

演变过程

但从算法逐步优化角度而言，动态规划更多是从如下方式进行演化：

暴力递归 -> 记忆化搜索 -> 动态规划

核心思想

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

demo2：青蛙跳台阶

2022-04-26_231911.png
（1）递归解法：

  1. var numWays = function (n) {
  2.     if (n <= 1) return 1;
  3.     if (n == 2) return 2;
  4.     return (numWays(n - 1) + numWays(n - 2)) % 1000000007;
  5. };

因为存在大量的重复计算（eg. f(9) = f(8)+(7)，f(8) = f(7)+(6)，会重复计算两次f(7)），所以会timeout…
（2）记忆化搜索：
因为递归有重复计算，所以引入了记忆化搜索，其思路很简单，将已经计算出来的结果存储起来，计算之前先查看是否已经被计算过，类似缓存的机制，其js中一般是通过Map来实现。

  1. const numWays = (() => {
  2.   const memo = {};
  3.   return (n) => {
  4.     if (n === 0 || n === 1) return 1;
  5.     if (!memo[n - 1]) memo[n - 1] = numWays(n - 1);
  6.     if (!memo[n - 2]) memo[n - 2] = numWays(n - 2);
  7.     return (memo[n - 1] + memo[n - 2]) % 1000000007;
  8.   };
  9. })();

(3)动态规划：

  1.     if(!n || n === 1) return 1;
  2.     let arr = [1, 1];
  3.     for(let i = 2; i <= n; i++) {
  4.         arr[i] = (arr[i - 1] + arr[i - 2]) % 1000000007;
  5.     }
  6.     return arr[n];

demo1：不同路径

2022-04-27_232154.png
（1）递归解法：

  1. var uniquePaths = function (m, n) {
  2.     var recursive = function (m, n, i, j) {
  3.         if (i == m - 1 || j == n - 1) return 1;
  4.         return recursive(m, n, i + 1, j) + recursive(m, n, i, j + 1);
  5.     }
  6.     return recursive(m, n, 0, 0);
  7. }

（2）记忆化搜索：
因为递归有重复计算，所以引入了记忆化搜索，其思路很简单，将已经计算出来的结果存储起来，计算之前先查看是否已经被计算过，类似缓存的机制，其js中一般是通过Map来实现。
(3)动态规划：

基础概念

无后效性

所谓的“无后效性”是指：当某阶段的状态一旦确定，此后的决策过程和最终结果将不受此前的各种状态所影响。
可简单理解为当编写好一个递归函数之后，当可变参数确定之后，结果是唯一确定的。

状态转移方程

很多博客都说什么状态转移方程，感觉说的很高大上，一般解题上来就是状态转移方程是xxxx，代码是xxxx，翻译下是什么意思呢？ 在求解第n个子问题的时候，通过已求解n-1个阶段的解和计算规则，可以得到第n个阶段时解。 即是最新的状态=目前的状态+决策。

初始化

很多题目解题的时候都说初始化，这并不是动态规划法的步骤。应该正确的去理解这些操作。动态规划在划分子问题求解顺序时，基本是先求解易求解最小的子问题，在由这些已经求解的阶段+计算规则，就能直接求得第n阶段的解。所以初始化的含义是，求得初始阶段的解。

边界条件

一般题目会说边界是啥，可以理解为怎么判断所有的子问题已经求解结束了。正常人也不会写while（true）吧，你总得让程序结束，判断你已经解决好这个问题了。

未完待续。。。
参考：
https://juejin.cn/post/6951922898638471181
https://juejin.cn/post/7069574174494162951
https://juejin.cn/post/6844904113889624077
https://juejin.cn/post/7029965326909440014
https://juejin.cn/post/6987204978884476959
https://juejin.cn/post/7049150280520171550
https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/submissions/