先了解一点，动态规划(Dynamic Programming)是一种思路，将一个复杂的问题分解为更简单的子问题，通过对每个子问题只求解一次并存储结果，这是一个自底向上的过程，通过定位已知和未知之间的关系来进行推导。

从本质上讲，这是一个简单的想法，在用给定的输入解决一个问题后，将结果保存为参考，以便将来使用，这样你就不必重新解决问题了…简而言之，就是 “记住你的过去”🫠。

这个方法可以用递归或者迭代算法来实现，递归算法是通过递归方式找到子问题的解决方案，迭代算法则是通过按特定顺序处理子问题来找到解决方案。(原地tp)

思路历程约等于递归+记忆搜索。当然，这和递归有区别，因为用递归的话，OJ会判定超时。

DP是如何工作的？

确定子问题:将主要问题划分为更小而独立的子问题。
存储解决方案:解决每个子问题并将解决方案存储在表格或者数组中。
建立解决方案:使用存好的解决方案建立主要问题的解决方案。
避免冗余:通过存储解决方案，DP可确保每个子问题只需要求解一次，从而减小计算时间。

什么时候使用动态规划？

两个必要条件:

最优子结构
重叠子问题

那么步骤呢？

确定他是否属于动态规划问题。
找到状态表达式。（倒推的过程）
确定状态和状态转换的关系。
制表（或者备忘录，反正和记忆搜索大差不差，就是现存储一些算好的结果，空间换时间）

爬楼梯

题目描述：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2 输出： 2 解释：有两种方法可以爬到楼顶。
1 阶 + 1 阶
2 阶

示例 2：输入： 3 输出： 3 解释：有三种方法可以爬到楼顶。
1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶
2 阶 + 1 阶

基于动态规划的思想分析

首先做到倒着分析，即:

定位到问题终点
站在终点的角度，思考后退的可能

这题为什么可以用动态规划？体现在——不管前面的决策如何，此后的状态必须基于当前状态的最优决策。比如爬楼梯，我们要想站在第n阶楼梯，该如何达到？无非两种情况：一种从n-1阶爬上来；一种是从n-2阶爬上来。即

f(n) = f(n-1) + f(n-2)(找到状态转移方程)

人话:站在n阶，往后退只能退一步或者两步，对于每一阶楼梯皆是如此。

f(n-2) = f(n-3) + f(n-4)

f(n-3) = f(n-4) + f(n-5)

…

这是一个重复计算的过程，也符合重叠子问题这一特征

可以把他转为一个树型模型

解法

我们已经找到了状态转移方程

f(n) = f(n-1) + f(n-2)

以 f(1) 和 f(2) 为起点，不断求和，循环递增 n 的值，我们就能够求出f(n)了

/**
 * @param {number} n
 * @return {number}
 */
const climbStairs = function (n) {
  // 初始化状态数组
  const dp = [];
  // 初始化已知值
  dp[1] = 1;
  dp[2] = 2;
  // 动态更新每一层楼梯对应的结果
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 2] + dp[i - 1];
  }
  // 返回目标值
  return dp[n];
};

分析技巧

递归思想明确树形思维模型：找到问题终点，思考倒退的姿势，往往可以帮助你更快速地明确状态间的关系
结合记忆化搜索，明确状态转移方程
递归代码转化为迭代表达（这一步不一定是必要的，1、2本身为思维路径，而并非代码实现。若你成长为熟手，2中分析出来的状态转移方程可以直接往循环里塞，根本不需要转换）。

不同路径

题目描述：一个机器人位于一个 m x n 网格的左上角（起始点标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（标记为 “Finish” ）。
问总共有多少条不同的路径？

输入：m = 3, n = 7 输出：28

输入：m = 3, n = 2 输出：3 解释：从左上角开始，总共有 3 条路径可以到达右下角。
向右 -> 向下 -> 向下
向下 -> 向下 -> 向右
向下 -> 向右 -> 向下

那么，先倒着分析，当前位置我们有哪些可选方向的

当前只能往下,dp[i][j] = dp[i-1][j]
当前只能往右,dp[i][j] = dp[i][j-1]
当前又能下又能右， dp[i][j]=dp[i][j−1]+dp[i−1][j]

那么状态转移方程势必为

dp[i][j] = dp[m - 1][n] + dp[m][n - 1];

为什么是-1？

没有为什么，因为起点是(0,0)，总共m行n列。

接着找初始条件，也就是起点

dp[0][0] = 1;

为什么初始条件是这个？

因为这是开始移动的起点，这个位置到自身的路径是唯一的。 (想一下，从(0,0)到(0,0)的方法是不是只有一种)

解法

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (m, n) {
  // 初始化一个 m x n 的二维数组
  let f = Array.from({ length: m }, () => Array(n).fill(0));
  f[0][0] = 1;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (i > 0) {
        f[i][j] += f[i - 1][j]; // 往下
      }
      if (j > 0) {
        f[i][j] += f[i][j - 1]; // 往右
      }
    }
  }
  return f[m - 1][n - 1];
};

还有一道晚点写

参考

Dynamic Programming or DP - GeeksforGeeks

前端算法与数据结构面试：底层逻辑解读与大厂真题训练 - 修言 - 掘金小册 (juejin.cn)

动态规划路径问题 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台

反思三道动态规划题

爬楼梯

基于动态规划的思想分析

解法

分析技巧

不同路径

解法