经典150题 - 多维动态规划

本篇归纳 LeetCode 面试经典 150 题中的**多维动态规划（Multidimensional DP）**专题。

涵盖典型方向：

网格与坐标路径：三角形最小路径和、最小路径和、不同路径 II
区间与回文子串：最长回文子串
双序列与字符串编辑：交错字符串、编辑距离
状态机与交易限制：买卖股票的最佳时机 III、买卖股票的最佳时机 IV
几何极值与矩阵：最大正方形

120. 三角形最小路径和

给定一个三角形 triangle，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上（若位于当前行的下标 i，下一步可移动至下一行的下标 i 或 i + 1）。

解题思路

逆向思维（自底向上）：从最底层向上推导，到达任意节点 (i, j) 的最小路径和等于其下方两个相邻节点的较小值加上自身值。到达顶点 (0, 0) 时即为全局最小路径和，无需任何边界特判与最终扫描。
状态转移方程： $d p [j] = min (d p [j], d p [j + 1]) + t r ian g l e [i] [j]$
空间优化（一维滚动数组）：初始化 dp 数组为三角形最后一整行（长度为 $n$ ），逐层向上覆盖更新。因为计算第 $j$ 列只需要旧的 $d p [j]$ 与 $d p [j + 1]$ ，正序更新不会覆盖后续未使用的状态，空间自然压缩至 $O (n)$ 。

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
    const n = triangle.length;
    // 1. 初始化 dp 为最底层那一行的完整状态副本
    const dp = [...triangle[n - 1]];
 
    // 2. 从倒数第二行（n - 2）自底向上递推至顶点（0）
    for (let i = n - 2; i >= 0; i--) {
        for (let j = 0; j <= i; j++) {
            // 当前格子的最小和 = 下方两个相邻分支的较小值 + 当前节点的值
            dp[j] = Math.min(dp[j], dp[j + 1]) + triangle[i][j];
        }
    }
 
    // 3. 自底向上推导的结果最终天然汇聚在顶点
    return dp[0];
};

时间复杂度： $O (n^{2})$ ，总节点数 $\sum_{i = 1}^{n} i = \frac{n ( n + 1 )}{2}$ ，每个节点仅做常数次加法和比较。
空间复杂度： $O (n)$ ，仅需一个长度为 $n$ 的一维数组；若允许原地修改输入数组，可达成 $O (1)$ 辅助空间。

64. 最小路径和

给定一个包含非负整数的 $m \times n$ 网格 grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。每次只能向下或向右移动一步。

解题思路

状态定义：dp[i][j] 表示从起点 (0, 0) 到达坐标 (i, j) 的最小路径和。
状态转移：对于一般的内部网格，只能从正上方或正左方走来，取较小者并累加当前格数值： $d p [i] [j] = min (d p [i - 1] [j], d p [i] [j - 1]) + g r i d [i] [j]$
边界处理：
- 第 0 行只能从左向右单向延伸（前缀和累加）。
- 第 0 列只能从正上方直落（前缀和累加）。
空间优化（一维滚动）：计算当前格只依赖上一行同列值 dp[j]（旧值）和当前行左侧值 dp[j-1]（新值），无需维护二维矩阵，开辟一行长度为 $n$ 的一维数组即可无副作用压缩至 $O (n)$ 。

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    // 使用一行数组缓存状态，保持函数纯净不污染输入入参
    const dp = new Array(n).fill(0);
 
    // 1. 初始化第一行：只能从起点向右单向延伸（前缀和）
    dp[0] = grid[0][0];
    for (let j = 1; j < n; j++) {
        dp[j] = dp[j - 1] + grid[0][j];
    }
 
    // 2. 逐行向下滚动递推
    for (let i = 1; i < m; i++) {
        // 第 0 列：只能从正上方走下来（dp[0] 为上一行的旧值）
        dp[0] = dp[0] + grid[i][0];
 
        // 其余内部格子：比较【上方 dp[j]】与【左侧 dp[j-1]】的较小值
        for (let j = 1; j < n; j++) {
            dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
        }
    }
 
    return dp[n - 1];
};

时间复杂度： $O (m \times n)$ ，其中 $m$ 和 $n$ 分别为网格行数与列数，遍历矩阵中每个格子一次。
空间复杂度： $O (n)$ ，使用长度为列数的一维滚动数组；若直接在原矩阵上原地累加，空间可降为 $O (1)$ 。

63. 不同路径 II

一个机器人位于一个 $m \times n$ 网格的左上角，试图到达网格的右下角。网格中的一些格子被标记为障碍物（1 表示障碍物，0 表示空地）。机器人每次只能向下或向右移动一步。求到达右下角的不同路径数。

解题思路

计数型 DP 与加法原理：不同于求极值的路径问题，本题求路径方案总数。对于无障碍物的平地，到达当前格的方案数等于上方方案数加上左方方案数： $d p [i] [j] = d p [i - 1] [j] + d p [i] [j - 1]$
障碍物截断：若 obstacleGrid[i][j] === 1，则该格子完全不可通行，到达该位置的路径数直接归零：dp[i][j] = 0。
边界防御：
- 起点 obstacleGrid[0][0] === 1 或终点 obstacleGrid[m-1][n-1] === 1，整个通路被直接封死，返回 0。
空间优化（一维滚动）：使用长度为 $n$ 的一维数组缓存状态。旧 dp[j] 对应上方格子方案数，dp[j-1] 对应左方格子方案数。遇到障碍物直接置 0，平地累加 dp[j] += dp[j-1]，自然压缩至 $O (n)$ 。

/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function(obstacleGrid) {
    const m = obstacleGrid.length;
    const n = obstacleGrid[0].length;
 
    // 1. 防御性特判：起点或终点本身就是障碍物，直接不可达
    if (obstacleGrid[0][0] === 1 || obstacleGrid[m - 1][n - 1] === 1) {
        return 0;
    }
 
    // 2. 一维滚动数组：dp[j] 表示到达当前行第 j 列的路径方案数
    const dp = new Array(n).fill(0);
    dp[0] = 1; // 起点有效，初始方案数为 1
 
    // 3. 逐行向下滚动递推
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (obstacleGrid[i][j] === 1) {
                // 障碍物：到达此处的路径数为 0，同时打断后续从该处向下转移
                dp[j] = 0;
            } else if (j > 0) {
                // 平地且不是第 0 列：当前方案数 = 上方方案数(旧 dp[j]) + 左方方案数(dp[j-1])
                dp[j] += dp[j - 1];
            }
        }
    }
 
    return dp[n - 1];
};

时间复杂度： $O (m \times n)$ ，扫描整个矩阵一次。
空间复杂度： $O (n)$ ，使用长度为列数的一维滚动数组。

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

解题思路

区间型 DP（洋葱模型）：
- 状态定义：dp[i][j] 表示子串 s[i..j] 是否是回文串。
- 转移逻辑：当 s[i] === s[j] 时：
  - 若区间长度 $\leq 3$ （ $j - i \leq 2$ ），如 "a", "aa", "aba"，首尾相等则天然为回文：dp[i][j] = true。
  - 若区间长度 $> 3$ ，剥掉首尾取决于内部子串：dp[i][j] = dp[i + 1][j - 1]。
遍历顺序关键（地基依赖）：
- 因为 dp[i][j] 依赖于其左下方的状态 dp[i + 1][j - 1]（正下方下一行），因此外层行号 $i$ 必须倒序遍历（let i = len - 1; i >= 0; i--），自底向上先算好大行号地基；
- 内层列号 $j$ 必须从 $i$ 开始正序向右（let j = i; j < len; j++），确保区间右端点永远在左端点右侧（只计算主对角线及右上三角）。
截取优化：循环内部仅记录 start = i 与 maxLen = j - i + 1，退出循环后只执行一次 s.slice(start, start + maxLen)，避免频繁产生垃圾临时字符串。

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    const len = s.length;
    if (len < 2) return s;
 
    // dp[i][j] 表示 s[i..j] 是否为回文串
    const dp = Array.from({ length: len }, () => new Array(len).fill(false));
    let start = 0;
    let maxLen = 1;
 
    // 外层 i 倒序（自底向上建楼），内层 j 正序（只算有效区间）
    for (let i = len - 1; i >= 0; i--) {
        for (let j = i; j < len; j++) {
            if (s[i] === s[j]) {
                if (j - i <= 2) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = dp[i + 1][j - 1];
                }
            }
 
            // 维护最长回文子串起点与长度
            if (dp[i][j] && (j - i + 1 > maxLen)) {
                maxLen = j - i + 1;
                start = i;
            }
        }
    }
 
    return s.slice(start, start + maxLen);
};

时间复杂度： $O (n^{2})$ ，双层循环遍历所有子串区间。
空间复杂度： $O (n^{2})$ ，维护 $n \times n$ 的区间状态表（注：中心扩展法可达到 $O (1)$ 空间，但区间 DP 表是分割回文等进阶问题的母体基石）。

97. 交错字符串

给定三个字符串 s1、s2、s3，请帮忙验证 s3 是否由 s1 和 s2 交错组成。

解题思路

第一道防线（长度剪枝）：若 s1.length + s2.length !== s3.length，总字符数不匹配，直接返回 false。
状态定义（前缀法）：dp[i][j] 表示 s1 的前 $i$ 个字符与 s2 的前 $j$ 个字符，能否交错拼成 s3 的前 $i + j$ 个字符。
状态转移：
- 当前目标字符为 s3[i + j - 1]，它只能由两方之一提供：
  1. 来自 s1[i - 1]：要求上一状态有效且字符吻合，即 dp[i - 1][j] && s1[i - 1] === s3[i + j - 1]；
  2. 来自 s2[j - 1]：要求左侧状态有效且字符吻合，即 dp[i][j - 1] && s2[j - 1] === s3[i + j - 1]；
- 转移方程： $d p [i] [j] = fromS1 \lor fromS2$ 。
空间进阶优化（一维滚动）：计算 dp[i][j] 仅依赖正上方旧值 dp[j] 与正左方新值 dp[j - 1]，可将 $(m + 1) \times (n + 1)$ 的二维表格无缝压缩为长度为 $n + 1$ 的一维数组，空间降至 $O (n)$ 。

/**
 * @param {string} s1
 * @param {string} s2
 * @param {string} s3
 * @return {boolean}
 */
// 进阶解法：一维滚动数组空间优化版
var isInterleave = function(s1, s2, s3) {
    if (s1.length + s2.length !== s3.length) return false;
 
    const m = s1.length;
    const n = s2.length;
    // 空间优化：只维护长度为 n + 1 的一维数组
    const dp = new Array(n + 1).fill(false);
 
    // 1. 初始化第 0 行（只用 s2 匹配 s3 前缀）
    dp[0] = true;
    for (let j = 1; j <= n; j++) {
        dp[j] = dp[j - 1] && (s2[j - 1] === s3[j - 1]);
    }
 
    // 2. 逐行向下滚动递推
    for (let i = 1; i <= m; i++) {
        // 更新当前行第 0 列（旧 dp[0] 为上一行第 0 列）
        dp[0] = dp[0] && (s1[i - 1] === s3[i - 1]);
 
        for (let j = 1; j <= n; j++) {
            // dp[j] 未覆写前代表上一行正上方，dp[j-1] 为当前行正左方
            const fromS1 = dp[j] && (s1[i - 1] === s3[i + j - 1]);
            const fromS2 = dp[j - 1] && (s2[j - 1] === s3[i + j - 1]);
 
            dp[j] = fromS1 || fromS2;
        }
    }
 
    return dp[n];
};

时间复杂度： $O (m \times n)$ ，其中 $m, n$ 分别为 s1, s2 的长度。
空间复杂度： $O (n)$ （优化前为 $O (m \times n)$ ，一维滚动后仅需 $O (min (m, n))$ ）。

72. 编辑距离

给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数。可以进行三种操作：插入一个字符、删除一个字符、替换一个字符。

解题思路

待补充

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function(word1, word2) {
 
};

时间复杂度：
空间复杂度：

123. 买卖股票的最佳时机 III

给定一个数组，它的第 $i$ 个元素是一支给定的股票在第 $i$ 天的价格。你最多可以完成两笔交易。注意：你不能同时参与多笔交易（必须在再次购买前出售掉之前的股票）。

解题思路

待补充

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
 
};

时间复杂度：
空间复杂度：

188. 买卖股票的最佳时机 IV

给你一个整数数组 prices 和一个整数 k，其中 prices[i] 是某支给定的股票在第 $i$ 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 $k$ 笔交易。

解题思路

待补充

/**
 * @param {number} k
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(k, prices) {
 
};

时间复杂度：
空间复杂度：

221. 最大正方形

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

解题思路

待补充

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalSquare = function(matrix) {
 
};

时间复杂度：
空间复杂度：

核心套路与备忘

模型分类	常见状态定义方式	代表题
网格坐标型	`dp[i][j]` 表示到达坐标 `(i, j)` 的极值或路径数	120. 三角形最小路径和、64. 最小路径和、63. 不同路径 II
区间型	`dp[i][j]` 表示子区间 `[i..j]` 是否回文或最值	5. 最长回文子串
双序列匹配型	`dp[i][j]` 表示前缀 $A [0.. i - 1]$ 与 $B [0.. j - 1]$ 的匹配代价或有效性	97. 交错字符串、72. 编辑距离
状态机与交易限制	`dp[i][k][0/1]` 结合天数、交易次数与持仓状态分类讨论	123. 股票 III、188. 股票 IV
几何区域型	`dp[i][j]` 以 `(i, j)` 为右下角满足条件的图形边界/边长	221. 最大正方形

description	三角形最小路径和(120)、最小路径和(64)、不同路径II(63)、最长回文子串(5)、交错字符串(97)、编辑距离(72)、买卖股票的最佳时机III(123)、买卖股票的最佳时机IV(188)、最大正方形(221)等多维动态规划题目
tags	leetcode, 经典150, 动态规划, 多维动态规划
aliases	经典150多维动态规划, 多维动态规划

unbrain · 算法学习 Wiki & 个人档案

探索

经典150题 - 多维动态规划

120. 三角形最小路径和

64. 最小路径和

63. 不同路径 II

5. 最长回文子串

97. 交错字符串

72. 编辑距离

123. 买卖股票的最佳时机 III

188. 买卖股票的最佳时机 IV

221. 最大正方形

核心套路与备忘

相关笔记

关系图谱

目录

反向链接