算法动态规划

反思三道动态规划题

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

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

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

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

DP是如何工作的？

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

什么时候使用动态规划？

两个必要条件:

  • 最优子结构
  • 重叠子问题

那么步骤呢？

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

爬楼梯

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

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

示例 1：

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

  1. 1 阶 + 1 阶
  2. 2 阶

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

  1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 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)了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* @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. 结合记忆化搜索，明确状态转移方程
  3. 递归代码转化为迭代表达（这一步不一定是必要的，1、2本身为思维路径，而并非代码实现。若你成长为熟手，2中分析出来的状态转移方程可以直接往循环里塞，根本不需要转换）。

不同路径

题目描述：一个机器人位于一个 m x n 网格的左上角 （起始点标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（标记为 “Finish” ）。

问总共有多少条不同的路径？

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

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

  1. 向右 -> 向下 -> 向下
  2. 向下 -> 向下 -> 向右
  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]

那么状态转移方程势必为

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

为什么是-1？

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

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

1
dp[0][0] = 1

为什么初始条件是这个？

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

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @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）全球极客挚爱的技术成长平台