用 “走楼梯” 讲透动态规划！4 个前端场景 + 4 道 LeetCode 题手把手教

动态规划：

如果说算法是解决问题的“套路”，那动态规划就是一种“拆解问题、巧用经验”的套路。它的核心思路可以用一句话概括：把复杂问题拆成小问题，记住小问题的答案，避免重复计算。

先看一个生活例子：算楼梯台阶

假设你要上10级台阶，每次只能走1级或2级，一共有多少种走法？

直接算10级很难，不如拆成小问题：

• 上10级的最后一步，要么是从第9级走1级，要么是从第8级走2级。
• 所以，10级的走法 = 9级的走法 + 8级的走法。
• 同理，9级的走法 = 8级的走法 + 7级的走法……
• 直到最基础的情况：1级只有1种走法，2级有两种走法（1+1或2）。

这里的关键是：后面的答案依赖前面的答案，而前面的答案可以重复利用。 我们不用每次都重新算，只要把算过的结果记下来（比如用一个数组存起来），就能一步步推导出最终答案。这就是动态规划的核心：用子问题的解推导父问题的解，并用“备忘录”保存子问题答案。

动态规划的3个核心要素

1. 状态定义：

用一个“变量”描述子问题的核心。比如上面的例子中，dp[n]代表"上n级台阶的走法数"，这个dp[n]就是“状态”。

2. 状态转移方程：

子问题之间的关系。比如dp[n] = dp[n-1] + dp[n-2]，就是用n-1和n-2的解推导n的解。

3. 初始条件：

最基础的子问题答案。比如dp[1] = 1, dp[2] = 2,没有这些“起点”，就无法推导后面的结果。

为什么要用动态规划？

最大的好处是减少重复计算。

比如算10级台阶时，如果不用动态规划，可能会递归计算dp[9]和dp[8]，而算dp[9]时又会重复算dp[8]和dp[7]……越往后重复越多，效率越低。

动态规划通过“记录子问题答案”，让每个子问题只算一次，把时间复杂度从指数级降到线性级（比如上面的例子，从O(2ⁿ)降到O(n)）。

前端开发中的常见场景

1. 路径规划：

比如网格类组件（如地图、表格）中，计算从左上角到右下角的最短路径（每次只能右移或下移），可以用动态规划拆解为“当前格子的最短路径=左边格子的路径 + 上边格子的路径”。

2. 最长公共子序列：

比较两个字符串的相似性（如文本diff功能），比如“abcde”和“ace”的最长公共子序列是“ace”，可以用动态规划一步步对比字符。

3. 资源分配：

比如前端性能优化中，给多个任务分配有限的时间/内存，求最大收益（类似“背包问题”），用动态规划决定每个任务分配多少资源。

4. 状态记忆：

比如在表单中，记录用户每一步的输入状态，回退时直接复用之前的结果，避免重新计算（本质是用“备忘录”保存子状态）。

以leetcode第64题为例演示路径规划

代码如下：

/*** @param {number[][]} grid* @return {number}*/
var minPathSum = function(grid) {if(grid.length === 0 || grid[0].length === 0) {return 0;}const rows = grid.length;const cols = grid[0].length;const dp = new Array(rows);for(let i = 0; i < rows; i++) {dp[i] = new Array(cols).fill(0)}// 初始条件 dp[0][0] = grid[0][0];// 第一行for(let j = 1; j < cols; j++) {dp[0][j] = dp[0][j-1] + grid[0][j]}// 第一列for(let i = 1; i < rows; i++) {dp[i][0] = dp[i-1][0] + grid[i][0]}for(let i = 1; i < rows; i++) {for(let j = 1; j < cols; j++) {dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1])}}return dp[rows-1][cols-1];
};// 测试用例
const grid1 = [[1, 3, 1],[1, 5, 1],[4, 2, 1]
];
console.log("网格1的最短路径和:", minPathSum(grid1)); // 输出：7，路径是 1→3→1→1→1const grid2 = [[1, 2, 3],[4, 5, 6]
];
console.log("网格2的最短路径和:", minPathSum(grid2)); // 输出：12，路径是 1→2→3→6

以leetcode第1143题为例演示最长公共子序列

代码如下：

var longestCommonSubsequence = function(text1, text2) {const m = text1.length;const n = text2.length;const dp = new Array(m+1).fill(0).map(() => new Array(n+1).fill(0))for(let i = 1; i <= m; i++) {for(let j = 1; j <= n; j++) {if(text1[i-1] === text2[j-1]) {dp[i][j] = dp[i-1][j-1] + 1;} else {dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])}}}return dp[m][n];
};// 测试用例
console.log(longestCommonSubsequence("abcde", "ace")); // 输出：3（公共子序列为"ace"）
console.log(longestCommonSubsequence("abc", "abc"));   // 输出：3（公共子序列为"abc"）
console.log(longestCommonSubsequence("abc", "def"));   // 输出：0（无公共子序列）

以leetcode第455题（分发饼干）为例演示贪心分配

代码如下：

var findContentChildren = function(g, s) {// 对胃口和饼干尺寸排序g.sort((a, b) => a - b);s.sort((a, b) => a - b);let i = 0; // 孩子指针let j = 0; // 饼干指针let count = 0; // 满足孩子的数量while(i < g.length && j < s.length) {if(s[j] >= g[i]) {count++;i++;j++;} else {// 饼干小，尝试更大尺寸的饼干j++;}} return count;
};// 测试用例
console.log(findContentChildren([1,2,3], [1,1])); // 1
console.log(findContentChildren([1,2], [1,2,3])); // 2
console.log(findContentChildren([2,3,4], [1,3,5])); // 2（3满足2，5满足3）

以leetcode第509题（经典的斐波那契数列）为例演示状态记忆

var fib = function(n) {const memo = new Array(n + 1).fill(-1);const dfs = (k) => {if(k === 0) return 0;if(k === 1) return 1;if(memo[k] !== -1) return memo[k];memo[k] = dfs(k - 1) + dfs(k - 2);return memo[k]}return dfs(n)
};// 测试用例
console.log(fib(2)); // 1
console.log(fib(3)); // 2
console.log(fib(4)); // 3

总结：

动态规划就像“走楼梯时，记住每一级台阶有几种走法，不用每次都从头数”。它通过拆解问题、记录中间结果，让复杂问题变得简单高效，是前端处理“有依赖关系的多步骤问题”的利器。

---