前端必备动态规划：10道经典题目详解（DP五部曲实战）
动态规划是前端算法面试的高频考点。本文通过「DP五部曲」框架，手把手带你掌握10道前端必备的DP题目，从基础递推到背包问题，每道题都包含详细注释、易错点分析和前端实际应用场景。
动态规划零基础的可以先补下
一、动态规划五部曲（核心框架）
无论什么DP问题，都可以按以下5个步骤拆解，这是解决DP问题的「万能钥匙」：
-
确定dp数组及下标的含义：明确
dp[i]（或二维 dp[i][j]）代表什么物理意义（比如"第i阶台阶的爬法数"）
-
确定递推公式：找到
dp[i] 与子问题 dp[i-1]/dp[i-2] 等的依赖关系（核心）
-
dp数组如何初始化：根据问题边界条件，初始化无法通过递推得到的基础值
-
确定遍历顺序：保证计算
dp[i] 时，其依赖的子问题已经被计算完成
-
打印dp数组（验证）：通过打印中间结果，验证递推逻辑是否正确（调试必备）
下面结合具体问题，逐一实战这套框架。
二、入门级（3道，理解DP核心三步法，必刷）
1. LeetCode70. 爬楼梯 ★
题目链接：70. 爬楼梯
难度：简单
核心：单状态转移，入门必做，会基础版 + 空间优化版
前端场景：步数计算、递归转迭代优化、分页器跳转步数计算、游戏角色移动路径数计算
题目描述：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
DP五部曲分析
-
dp数组含义：
dp[i] 表示爬到第i阶台阶的不同方法数
-
递推公式：
dp[i] = dp[i-1] + dp[i-2]（到第i阶的方法=到i-1阶爬1步 + 到i-2阶爬2步）
-
初始化：
dp[1] = 1（1阶只有1种方法），dp[2] = 2（2阶有2种方法）
-
遍历顺序：从左到右（i从3到n）
-
打印验证：遍历过程中打印
dp[i]，验证方法数是否符合预期
完整版代码（二维DP思想，但实际用一维数组）
/**
* LeetCode70. 爬楼梯
* 时间复杂度：O(n)
* 空间复杂度：O(n)
*/
function climbStairs(n) {
// 【步骤1】确定dp数组及下标的含义
// dp[i] 表示爬到第i阶台阶的不同方法数
const dp = new Array(n + 1);
// 【步骤3】dp数组如何初始化
// 边界条件：1阶只有1种方法，2阶有2种方法
if (n === 1) return 1;
if (n === 2) return 2;
dp[1] = 1; // 1阶：只有1种方法（直接爬1阶）
dp[2] = 2; // 2阶：有2种方法（1+1 或 2）
// 【步骤4】确定遍历顺序：从左到右，保证计算dp[i]时dp[i-1]和dp[i-2]已计算
for (let i = 3; i <= n; i++) {
// 【步骤2】确定递推公式
// 到达第i阶只有两种方式：
// 1. 从第i-1阶爬1步到达 → 方法数 = dp[i-1]
// 2. 从第i-2阶爬2步到达 → 方法数 = dp[i-2]
// 总方法数 = 两种方式的方法数之和（加法原理）
dp[i] = dp[i - 1] + dp[i - 2];
// 【步骤5】打印dp数组（验证） - 调试时可以取消注释
// console.log(`dp[${i}] = ${dp[i]}`);
}
return dp[n];
}
// 测试用例
console.log(climbStairs(2)); // 2
console.log(climbStairs(3)); // 3
console.log(climbStairs(4)); // 5
console.log(climbStairs(5)); // 8
空间优化版（滚动数组）
/**
* 空间优化版：滚动数组
* 时间复杂度：O(n)
* 空间复杂度：O(1) ← 从O(n)优化到O(1)
*
* 【优化思路】
* 观察递推公式：dp[i] = dp[i-1] + dp[i-2]
* 发现dp[i]只依赖前两个状态，不需要保存整个数组
* 可以用三个变量滚动更新：prevPrev(dp[i-2]), prev(dp[i-1]), cur(dp[i])
*/
function climbStairs(n) {
// 【易错点1】边界处理：n=1或n=2时需要提前返回
// 如果n=1时进入循环，prevPrev=1, prev=2会计算出错误结果
if (n === 1) return 1;
if (n === 2) return 2;
// 初始化：对应dp[1]=1, dp[2]=2
let prevPrev = 1; // dp[i-2]，初始表示dp[1]=1
let prev = 2; // dp[i-1]，初始表示dp[2]=2
let cur;
// 从第3阶开始计算
for (let i = 3; i <= n; i++) {
// 计算当前阶的方法数
cur = prevPrev + prev;
// 【易错点2】滚动更新顺序很重要：先更新prevPrev，再更新prev
// 如果顺序错误（如先更新prev），会导致prevPrev获取到错误的值
prevPrev = prev; // 下一轮的dp[i-2] = 当前的dp[i-1]
prev = cur; // 下一轮的dp[i-1] = 当前的dp[i]
}
return cur;
}
前端应用场景：
-
分页器组件：计算从第1页跳转到第n页的不同路径数（每次可以跳1页或2页）
-
游戏开发：角色在台阶上移动，每次可以走1步或2步，计算到达目标位置的方案数
-
动画路径计算：计算元素从位置A到位置B的不同动画路径数量
2. LeetCode53. 最大子数组和 ★
题目链接：53. 最大子数组和
难度：简单
核心：贪心 + DP 结合，理解「状态转移的条件选择」
前端场景：数据趋势统计、收益/数值最值分析、股票K线图最大收益区间、用户行为数据峰值分析
题目描述：
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
DP五部曲分析
-
dp数组含义：
dp[i] 表示以 nums[i] 为结尾的最大子数组和（注意：必须以nums[i]结尾）
-
递推公式：
dp[i] = Math.max(nums[i], dp[i-1] + nums[i])（要么重新开始，要么延续前面的和）
-
初始化：
dp[0] = nums[0]（第一个元素的最大子数组和就是它自己）
-
遍历顺序：从左到右（i从1到n-1）
-
打印验证：打印dp数组，找到最大值
完整版代码
/**
* LeetCode53. 最大子数组和
* 时间复杂度：O(n)
* 空间复杂度：O(n)
*/
function maxSubArray(nums) {
const len = nums.length;
// 【易错点1】边界处理：空数组返回0
if (len === 0) return 0;
if (len === 1) return nums[0];
// 【步骤1】确定dp数组及下标的含义
// dp[i] 表示以nums[i]为结尾的最大子数组和（注意：必须以nums[i]结尾）
// 这个定义很关键：保证子数组是连续的
const dp = new Array(len);
// 【步骤3】dp数组如何初始化
// 第一个元素的最大子数组和就是它自己（没有前面的元素可以延续）
dp[0] = nums[0];
// 用于记录全局最大值（因为dp[i]只表示以i结尾的最大和，不一定全局最大）
let maxSum = dp[0];
// 【步骤4】确定遍历顺序：从左到右
for (let i = 1; i < len; i++) {
// 【步骤2】确定递推公式
// 核心思想：如果前面的和是负数，不如重新开始（贪心思想）
// 两种选择：
// 1. 重新开始：只选当前元素nums[i]（前面的和是负数，拖累总和）
// 2. 延续前面的：dp[i-1] + nums[i]（前面的和是正数，可以继续累加）
dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
// 【易错点2】必须实时更新全局最大值
// 因为dp[i]只是以i结尾的最大和，最终答案不一定是dp[len-1]
maxSum = Math.max(maxSum, dp[i]);
// 【步骤5】打印验证
// console.log(`dp[${i}] = ${dp[i]}, maxSum = ${maxSum}`);
}
return maxSum;
}
// 测试用例
console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6
console.log(maxSubArray([1])); // 1
console.log(maxSubArray([5, 4, -1, 7, 8])); // 23
console.log(maxSubArray([-1])); // -1
空间优化版（只需一个变量）
/**
* 空间优化版：滚动变量
* 时间复杂度：O(n)
* 空间复杂度：O(1) ← 从O(n)优化到O(1)
*
* 【优化思路】
* dp[i]只依赖dp[i-1]，不需要保存整个数组
* 用一个变量prev保存上一个状态即可
*/
function maxSubArray(nums) {
const len = nums.length;
if (len === 0) return 0;
if (len === 1) return nums[0];
// 用prev代替dp[i-1]，初始值为dp[0]
let prev = nums[0];
let maxSum = prev;
for (let i = 1; i < len; i++) {
// 计算当前状态：要么重新开始，要么延续前面的
prev = Math.max(nums[i], prev + nums[i]);
// 更新全局最大值
maxSum = Math.max(maxSum, prev);
}
return maxSum;
}
前端应用场景：
-
股票K线图：计算某段时间内买入卖出的最大收益（价格差的最大连续子数组和）
-
用户行为分析：分析用户在某段时间内的活跃度峰值（数据流的最大连续区间和）
-
性能监控：找到服务器响应时间最差的连续时间段（负值转换为响应时间）
-
数据可视化：在折线图中高亮显示数据增长最快的连续区间
3. LeetCode198. 打家劫舍 ★
题目链接：198. 打家劫舍
难度：简单
核心：状态转移的「条件限制」（相邻不选），基础空间优化
前端场景：资源筛选、最优选择问题、权限分配优化、任务调度（不能同时执行相邻任务）
题目描述：
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组 nums，请计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。
示例 1：
输入：nums = [1,2,3,1]
输出：4
解释：偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。总金额 = 1 + 3 = 4。
示例 2：
输入：nums = [2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 9），接着偷窃 5 号房屋（金额 = 1）。总金额 = 2 + 9 + 1 = 12。
DP五部曲分析
-
dp数组含义：
dp[i] 表示前i间房屋能偷到的最高金额
- 可以用二维状态：
dp[i][0] 表示第i间不偷，dp[i][1] 表示第i间偷
-
递推公式：
-
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1])（不偷当前，前一间可偷可不偷）
-
dp[i][1] = dp[i-1][0] + nums[i-1]（偷当前，前一间必须不偷）
-
初始化：
dp[0] = [0, 0]（前0间，偷或不偷都是0）
-
遍历顺序：从左到右（i从1到n）
-
打印验证：打印dp数组验证
完整版代码（二维状态）
/**
* LeetCode198. 打家劫舍
* 时间复杂度：O(n)
* 空间复杂度：O(n)
*/
function rob(nums) {
const len = nums.length;
// 【易错点1】边界处理
if (len === 0) return 0;
if (len === 1) return nums[0];
// 【步骤1】确定dp数组及下标的含义
// dp[i][0] = 前i间房屋，第i间不偷能获取的最高金额
// dp[i][1] = 前i间房屋，第i间偷能获取的最高金额
// 使用二维状态可以清晰地表达"相邻不能同时偷"的约束
const dp = new Array(len + 1);
// 【步骤3】dp数组如何初始化
// 前0间房屋：不偷和偷的金额都是0（没有房屋可偷）
dp[0] = [0, 0];
// 【步骤4】确定遍历顺序：从左到右
for (let i = 1; i <= len; i++) {
// 【易错点2】数组索引转换：dp[i]对应nums[i-1]
// dp[1]对应nums[0]（第1间房屋），dp[2]对应nums[1]（第2间房屋）
const curVal = nums[i - 1];
// 【步骤2】确定递推公式
// 状态1：第i间不偷 → 前i-1间可以偷也可以不偷，取最大值
const valNotThief = Math.max(...dp[i - 1]);
// 状态2：第i间偷 → 前i-1间必须不偷（相邻不能同时偷），加上当前金额
// 【易错点3】必须是dp[i-1][0]，不能是dp[i-1][1]（违反相邻规则）
const valThief = curVal + dp[i - 1][0];
// 更新当前状态
dp[i] = [valNotThief, valThief];
// 【步骤5】打印验证
// console.log(`dp[${i}] = [不偷:${valNotThief}, 偷:${valThief}]`);
}
// 最终结果：前len间房屋偷或不偷的最大值
return Math.max(...dp[len]);
}
// 测试用例
console.log(rob([1, 2, 3, 1])); // 4
console.log(rob([2, 7, 9, 3, 1])); // 12
console.log(rob([2, 1, 1, 2])); // 4
空间优化版（两个变量）
/**
* 空间优化版：滚动变量
* 时间复杂度：O(n)
* 空间复杂度：O(1) ← 从O(n)优化到O(1)
*
* 【优化思路】
* 观察递推公式：dp[i]只依赖dp[i-1]的两个值
* 可以用两个变量vNot和vYes滚动更新
*/
function rob(nums) {
const len = nums.length;
if (len === 0) return 0;
if (len === 1) return nums[0];
// 初始化：对应dp[0] = [0, 0]
let vNot = 0; // 前i间不偷的最大值
let vYes = 0; // 前i间偷的最大值
for (let i = 1; i <= len; i++) {
const curVal = nums[i - 1];
// 【易错点4】关键：提前保存上一轮的所有状态，避免更新时覆盖
// 如果直接使用vNot和vYes，更新vNot时可能会用到已经更新的vYes值
const prevNot = vNot;
const prevYes = vYes;
// 不偷当前间：上一轮偷或不偷的最大值
vNot = Math.max(prevNot, prevYes);
// 偷当前间：上一轮不偷的最大值 + 当前金额
// 【易错点5】必须用prevNot，不能用vNot（因为vNot已经更新了）
vYes = curVal + prevNot;
}
return Math.max(vNot, vYes);
}
前端应用场景：
-
任务调度：在任务列表中，某些任务不能同时执行（有依赖关系），求最大收益
-
权限分配：某些权限不能同时授予（互斥权限），求最大权限价值组合
-
资源选择：在资源列表中，相邻资源有冲突，求最优选择方案
-
广告投放优化：相邻时段的广告不能同时投放，求最大收益的投放方案
三、经典应用级（4道，DP核心考点，高频考）
4. LeetCode62. 不同路径 ★
题目链接：62. 不同路径
难度：中等
核心：二维DP基础（可优化为一维），理解「路径型DP」
前端场景：可视化布局路径计算、网格类问题、Canvas/SVG路径绘制、游戏地图路径规划
题目描述：
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 "Start" ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 "Finish"）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7
输出：28
示例 2：
输入：m = 3, n = 2
输出：3
解释：从左上角开始，总共有 3 条路径可以到达右下角：
1. 向右 → 向下 → 向下
2. 向下 → 向下 → 向右
3. 向下 → 向右 → 向下
DP五部曲分析
-
dp数组含义：
dp[i][j] 表示从起点(0,0)走到位置(i,j)的不同路径数
-
递推公式：
dp[i][j] = dp[i-1][j] + dp[i][j-1]（只能从上方或左方来）
-
初始化：
- 第一行所有位置：
dp[0][j] = 1（只能从左边来）
- 第一列所有位置：
dp[i][0] = 1（只能从上边来）
-
遍历顺序：从上到下、从左到右（双重循环）
-
打印验证：打印dp数组验证
完整版代码（二维DP）
/**
* LeetCode62. 不同路径
* 时间复杂度：O(m * n)
* 空间复杂度：O(m * n)
*/
function uniquePaths(m, n) {
// 【步骤1】确定dp数组及下标的含义
// dp[i][j] 表示从左上角(0,0)走到位置(i,j)的不同路径数
// 为了方便处理边界，使用dp[i+1][j+1]表示网格(i,j)的路径数
const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
// 【步骤3】dp数组如何初始化
// 第一行（i=1）：所有位置只能从左边来，路径数都是1
for (let j = 1; j <= n; j++) {
dp[1][j] = 1;
}
// 第一列（j=1）：所有位置只能从上边来，路径数都是1
for (let i = 1; i <= m; i++) {
dp[i][1] = 1;
}
// 【步骤4】确定遍历顺序：从上到下、从左到右
// 从(2,2)开始，因为第一行和第一列已经初始化
for (let i = 2; i <= m; i++) {
for (let j = 2; j <= n; j++) {
// 【步骤2】确定递推公式
// 走到(i,j)只有两种方式：
// 1. 从上方(i-1,j)向下走一步 → 路径数 = dp[i-1][j]
// 2. 从左方(i,j-1)向右走一步 → 路径数 = dp[i][j-1]
// 总路径数 = 两种方式的路径数之和（加法原理）
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
// 【步骤5】打印验证（调试时取消注释）
// console.log('DP数组：');
// for (let i = 1; i <= m; i++) {
// console.log(dp[i].slice(1).join(' '));
// }
return dp[m][n];
}
// 测试用例
console.log(uniquePaths(3, 7)); // 28
console.log(uniquePaths(3, 2)); // 3
console.log(uniquePaths(7, 3)); // 28
空间优化版（一维DP）
/**
* 空间优化版：一维DP
* 时间复杂度：O(m * n)
* 空间复杂度：O(n) ← 从O(m*n)优化到O(n)
*
* 【优化思路】
* 观察递推公式：dp[i][j] = dp[i-1][j] + dp[i][j-1]
* 计算第i行时，只需要用到：
* 1. 上一行第j列的值（dp[i-1][j]）→ 对应更新前的dp[j]
* 2. 当前行第j-1列的值（dp[i][j-1]）→ 对应更新后的dp[j-1]
* 可以用一维数组dp[j]滚动更新
*/
function uniquePaths(m, n) {
// 【步骤1】一维dp数组：dp[j]表示当前行第j列的路径数
// 初始化为第一行的值：所有位置路径数都是1（只能从左边来）
const dp = new Array(n + 1).fill(1);
// 【步骤4】确定遍历顺序：从第2行开始遍历
for (let i = 2; i <= m; i++) {
// 【易错点1】j从2开始，因为第1列（j=1）的值永远是1（只能从上边来）
for (let j = 2; j <= n; j++) {
// 【步骤2】递推公式（一维版）
// dp[j]（更新前）= 上一行第j列的路径数（dp[i-1][j]）
// dp[j-1]（更新后）= 当前行第j-1列的路径数（dp[i][j-1]）
// 更新：dp[j] = dp[j]（旧值，来自上方）+ dp[j-1]（新值，来自左方）
dp[j] = dp[j] + dp[j - 1];
// 【易错点2】注意：这里dp[j-1]是已经更新的值（当前行），
// 而dp[j]是旧值（上一行），正好符合递推公式的需求
}
}
return dp[n];
}
前端应用场景：
-
Canvas/SVG路径绘制：计算从起点到终点的不同绘制路径数量
-
游戏地图：计算角色从起点到终点的移动方案数（只能向右或向下）
-
网格布局计算：在CSS Grid或Flex布局中，计算元素排列的不同路径数
-
路由规划：在地图应用中，计算从A点到B点的不同路线数量
5. LeetCode63. 不同路径 II
题目链接：63. 不同路径 II
难度：中等
核心：带障碍的路径DP，学会「状态转移的边界判断」
前端场景：网格布局中的障碍物处理、表单验证路径计算、游戏地图障碍物路径规划
题目描述：
一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 "Start" ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 "Finish"）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 → 向右 → 向下 → 向下
2. 向下 → 向下 → 向右 → 向右
示例 2：
输入：obstacleGrid = [[0,1],[0,0]]
输出：1
DP五部曲分析
-
dp数组含义：
dp[i][j] 表示从起点到达位置(i,j)的路径数
-
递推公式：
- 如果(i,j)是障碍物：
dp[i][j] = 0
- 否则：
dp[i][j] = dp[i-1][j] + dp[i][j-1]
-
初始化：
- 第一行：遇到障碍物前都是1，遇到障碍物后都是0
- 第一列：遇到障碍物前都是1，遇到障碍物后都是0
-
遍历顺序：从上到下、从左到右
-
打印验证：打印dp数组验证
完整版代码（二维DP）
/**
* LeetCode63. 不同路径 II（带障碍物）
* 时间复杂度：O(m * n)
* 空间复杂度：O(m * n)
*/
function uniquePathsWithObstacles(obstacleGrid) {
const m = obstacleGrid.length;
const n = obstacleGrid[0].length;
// 【易错点1】边界处理：起点或终点是障碍物，直接返回0
if (obstacleGrid[0][0] === 1 || obstacleGrid[m - 1][n - 1] === 1) {
return 0;
}
// 【步骤1】确定dp数组及下标的含义
// dp[i][j] 表示从起点到达位置(i-1,j-1)的路径数（索引从1开始便于处理边界）
const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
// 【步骤3】dp数组如何初始化
// 初始化第一行：只能从左边来，遇到障碍物则后续位置无法到达
for (let j = 1; j <= n; j++) {
const curGrid = obstacleGrid[0][j - 1]; // 网格索引转换
if (curGrid === 1) {
// 【易错点2】遇到障碍物，后续位置都无法到达，直接跳出
break;
}
dp[1][j] = 1;
}
// 初始化第一列：只能从上边来，遇到障碍物则后续位置无法到达
for (let i = 2; i <= m; i++) {
// 【易错点3】从i=2开始，因为dp[1][1]已在第一行初始化
const curGrid = obstacleGrid[i - 1][0];
if (curGrid === 1) {
break;
}
dp[i][1] = 1;
}
// 【步骤4】确定遍历顺序：从第2行第2列开始
for (let i = 2; i <= m; i++) {
for (let j = 2; j <= n; j++) {
// 网格索引转换：dp[i][j]对应网格(i-1, j-1)
const curGrid = obstacleGrid[i - 1][j - 1];
// 【步骤2】确定递推公式
if (curGrid === 1) {
// 【易错点4】当前位置是障碍物，无法到达，路径数为0
dp[i][j] = 0;
} else {
// 当前位置不是障碍物，可以从上方或左方到达
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[m][n];
}
空间优化版（一维DP）
/**
* 空间优化版：一维DP
* 时间复杂度：O(m * n)
* 空间复杂度：O(n)
*/
function uniquePathsWithObstacles(obstacleGrid) {
const m = obstacleGrid.length;
const n = obstacleGrid[0].length;
if (obstacleGrid[0][0] === 1 || obstacleGrid[m - 1][n - 1] === 1) {
return 0;
}
// 一维dp数组：dp[j]表示当前行第j列的路径数
const dp = new Array(n + 1).fill(0);
// 初始化第一行
for (let j = 1; j <= n; j++) {
const curGrid = obstacleGrid[0][j - 1];
if (curGrid === 1) break;
dp[j] = 1;
}
// 从第2行开始遍历
for (let i = 2; i <= m; i++) {
for (let j = 1; j <= n; j++) {
const curGrid = obstacleGrid[i - 1][j - 1];
if (curGrid === 1) {
// 【易错点5】障碍物位置路径数置0
dp[j] = 0;
} else if (j === 1) {
// 第一列：只能从上边来，保持dp[j]不变（如果上边是障碍物，dp[j]已经是0）
// 不需要更新，因为第一列的路径数在初始化时已经确定
} else {
// 非第一列：可以从上方或左方到达
dp[j] = dp[j] + dp[j - 1];
}
}
}
return dp[n];
}
前端应用场景：
-
表单验证：在复杂的多步骤表单中，某些步骤可能被禁用（障碍物），计算完成表单的不同路径
-
游戏地图：在游戏中，某些格子是障碍物，计算从起点到终点的路径数
-
权限路由：在权限系统中，某些路由节点被禁用，计算用户可访问的路由路径数
-
工作流设计：在工作流中，某些节点可能被跳过，计算完成流程的不同路径
6. LeetCode213. 打家劫舍 II
题目链接：213. 打家劫舍 II
难度：中等
核心：环形DP，拆分为两个基础DP问题（分治思想）
前端场景：环形资源分配、循环任务调度、权限系统中的循环依赖处理
题目描述：
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组 nums，请计算你在不触动警报装置的情况下，今晚能够偷窃到的最高金额。
示例 1：
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2），因为他们是相邻的。
示例 2：
输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。偷窃到的最高金额 = 1 + 3 = 4。
示例 3：
输入：nums = [1,2,3]
输出：3
DP五部曲分析（分治思想）
核心思路：环形问题转化为两个线性问题
- 情况1：不偷第一间（可以偷最后一间）→ 转换为线性问题：偷 [1, len-1]
- 情况2：不偷最后一间（可以偷第一间）→ 转换为线性问题：偷 [0, len-2]
- 取两种情况的最大值
完整版代码
/**
* LeetCode213. 打家劫舍 II（环形）
* 时间复杂度：O(n)
* 空间复杂度：O(n)
*/
function rob(nums) {
const len = nums.length;
// 【易错点1】边界处理
if (len === 0) return 0;
if (len === 1) return nums[0];
if (len === 2) return Math.max(nums[0], nums[1]);
// 【核心思路】环形问题拆分为两个线性问题
// 情况1：不偷第一间（可以偷最后一间）→ 范围 [1, len-1]
// 情况2：不偷最后一间（可以偷第一间）→ 范围 [0, len-2]
// 取两种情况的最大值
/**
* 辅助函数：线性数组的打家劫舍（LeetCode198的解法）
* @param {number[]} arr - 线性房屋数组
* @returns {number} - 能偷到的最大金额
*/
function robLinear(arr) {
const n = arr.length;
if (n === 0) return 0;
if (n === 1) return arr[0];
// 二维状态DP
const dp = new Array(n + 1);
dp[0] = [0, 0]; // 前0间：不偷和偷都是0
for (let i = 1; i <= n; i++) {
const curVal = arr[i - 1];
// 不偷当前间：前i-1间偷或不偷的最大值
const valNotThief = Math.max(...dp[i - 1]);
// 偷当前间：前i-1间必须不偷
const valThief = curVal + dp[i - 1][0];
dp[i] = [valNotThief, valThief];
}
return Math.max(...dp[n]);
}
// 情况1：不偷第一间，范围是nums[1]到nums[len-1]
const case1 = robLinear(nums.slice(1));
// 情况2：不偷最后一间，范围是nums[0]到nums[len-2]
const case2 = robLinear(nums.slice(0, len - 1));
// 【易错点2】返回两种情况的最大值
return Math.max(case1, case2);
}
// 测试用例
console.log(rob([2, 3, 2])); // 3
console.log(rob([1, 2, 3, 1])); // 4
console.log(rob([1, 2, 3])); // 3
空间优化版（使用滚动变量）
/**
* 空间优化版：robLinear函数使用滚动变量
*/
function rob(nums) {
const len = nums.length;
if (len === 0) return 0;
if (len === 1) return nums[0];
if (len === 2) return Math.max(nums[0], nums[1]);
// 辅助函数：线性数组打家劫舍（空间优化版）
function robLinear(arr) {
const n = arr.length;
if (n === 0) return 0;
if (n === 1) return arr[0];
let vNot = 0; // 不偷的最大值
let vYes = 0; // 偷的最大值
for (let i = 0; i < n; i++) {
const curVal = arr[i];
const prevNot = vNot;
const prevYes = vYes;
vNot = Math.max(prevNot, prevYes);
vYes = curVal + prevNot;
}
return Math.max(vNot, vYes);
}
const case1 = robLinear(nums.slice(1));
const case2 = robLinear(nums.slice(0, len - 1));
return Math.max(case1, case2);
}
前端应用场景：
-
循环任务调度：在循环列表中，某些任务不能同时执行，求最大收益的调度方案
-
环形权限分配：在权限环中，相邻权限互斥，求最大权限价值组合
-
资源循环利用：在循环资源池中，某些资源不能同时使用，求最优资源分配
-
时间轮调度：在时间轮算法中，计算最优的任务执行方案
7. LeetCode322. 零钱兑换 ★
题目链接：322. 零钱兑换
难度：中等
核心：完全背包基础版，理解「最值型DP」的状态转移
前端场景：金额/资源最优分配、最少步骤问题、支付找零算法、资源最小化配置
题目描述：
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
解释：无法凑成总金额 3
示例 3：
输入：coins = [1], amount = 0
输出：0
DP五部曲分析
-
dp数组含义：
dp[i][j] 表示用前i种硬币凑出金额j所需的最少硬币个数
-
递推公式：
- 不选第i种硬币：
dp[i][j] = dp[i-1][j]
- 选第i种硬币：
dp[i][j] = dp[i][j-coins[i-1]] + 1（注意是dp[i]不是dp[i-1]，因为可以重复选）
- 取最小值：
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-coins[i-1]] + 1)
-
初始化：
-
dp[0][0] = 0（0种硬币凑0元需要0个）
-
dp[0][j>0] = Infinity（0种硬币无法凑正数金额）
-
dp[i][0] = 0（凑0元永远需要0个）
-
遍历顺序：外层遍历硬币种类，内层遍历金额（正序，因为是完全背包）
-
打印验证：打印dp数组验证
完整版代码（二维DP）
/**
* LeetCode322. 零钱兑换（完全背包-最值型）
* 时间复杂度：O(coins.length * amount)
* 空间复杂度：O(coins.length * amount)
*/
function coinChange(coins, amount) {
const coinCount = coins.length;
const target = amount;
// 【易错点1】边界处理：凑0元直接返回0
if (target === 0) return 0;
// 【步骤1】确定dp数组及下标的含义
// dp[i][j] = 用前i种硬币凑出金额j所需的最少硬币个数
// 初始化：所有值先填Infinity（表示初始无法凑出）
const dp = new Array(coinCount + 1).fill(0).map(() => new Array(target + 1).fill(Infinity));
// 【步骤3】dp数组如何初始化
dp[0][0] = 0; // 0种硬币凑0元，需要0个
// 0种硬币凑正数金额，无法凑出（保持Infinity）
for (let j = 1; j <= target; j++) {
dp[0][j] = Infinity;
}
// 【步骤4】确定遍历顺序：外层遍历硬币种类，内层遍历金额（正序）
// 正序遍历是因为完全背包：每种硬币可以使用无限次
for (let i = 1; i <= coinCount; i++) {
dp[i][0] = 0; // 凑0元永远需要0个硬币
const curCoin = coins[i - 1]; // 【易错点2】数组索引转换：第i种硬币对应coins[i-1]
for (let j = 1; j <= target; j++) {
if (j < curCoin) {
// 金额不足，无法使用当前硬币，继承前i-1种硬币的结果
dp[i][j] = dp[i - 1][j];
} else {
// 【步骤2】确定递推公式
// 完全背包核心：用当前硬币时是dp[i][j-curCoin]+1（而非dp[i-1]）
// 因为硬币可以重复使用，所以用dp[i]（已经考虑了当前硬币）
dp[i][j] = Math.min(
dp[i - 1][j], // 不用第i种硬币
dp[i][j - curCoin] + 1 // 用第i种硬币（注意是dp[i]，可以重复选）
);
}
}
}
// 【易错点3】无法凑出时返回-1，而非Infinity
return dp[coinCount][target] === Infinity ? -1 : dp[coinCount][target];
}
// 测试用例
console.log(coinChange([1, 2, 5], 11)); // 3
console.log(coinChange([2], 3)); // -1
console.log(coinChange([1], 0)); // 0
空间优化版（一维DP）
/**
* 空间优化版：一维DP
* 时间复杂度：O(coins.length * amount)
* 空间复杂度：O(amount) ← 从O(coins.length * amount)优化到O(amount)
*
* 【优化思路】
* 观察递推公式：dp[i][j] = Math.min(dp[i-1][j], dp[i][j-coins[i-1]] + 1)
* 计算dp[i][j]时只需要：
* 1. 上一行第j列的值（dp[i-1][j]）→ 对应更新前的dp[j]
* 2. 当前行第j-coins[i-1]列的值（dp[i][j-coins[i-1]]）→ 对应更新后的dp[j-coins[i-1]]
* 可以用一维数组dp[j]正序遍历（完全背包特征：正序）
*/
function coinChange(coins, amount) {
const coinCount = coins.length;
const target = amount;
if (target === 0) return 0;
// 【步骤1】一维dp数组：dp[j] = 凑出金额j所需的最少硬币个数
const dp = new Array(target + 1).fill(Infinity);
// 【步骤3】初始化
dp[0] = 0; // 凑0元需要0个硬币
// 【步骤4】确定遍历顺序：外层遍历硬币，内层正序遍历金额
// 【易错点4】完全背包必须正序遍历：保证每种硬币可以使用无限次
// 如果倒序遍历，就变成了01背包（每种硬币只能用一次）
for (let i = 1; i <= coinCount; i++) {
const curCoin = coins[i - 1];
// 【易错点5】从curCoin开始遍历，避免j<curCoin的无效判断
for (let j = curCoin; j <= target; j++) {
// 【步骤2】递推公式（一维版）
// dp[j]（更新前）= 不用当前硬币的最少个数（上一轮的结果）
// dp[j - curCoin] + 1 = 用当前硬币的最少个数（当前轮已更新的结果）
dp[j] = Math.min(dp[j], dp[j - curCoin] + 1);
}
}
// 【易错点6】返回前检查是否为Infinity
return dp[target] === Infinity ? -1 : dp[target];
}
前端应用场景：
-
支付找零：在支付系统中，计算用最少硬币数找零给用户
-
资源最小化配置：在资源分配中，用最少的资源组合达到目标值
-
API调用优化：计算用最少的API调用次数完成某个任务
-
组件懒加载：计算用最少的组件加载次数完成页面渲染
8. LeetCode518. 零钱兑换 II
题目链接：518. 零钱兑换 II
难度：中等
核心：完全背包的「组合数型DP」，与322（最值型）做区分
前端场景：组合方案统计、支付方式组合数计算、资源配置方案数统计
题目描述：
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
示例 1：
输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2：
输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币无法凑成总金额 3。
示例 3：
输入：amount = 10, coins = [10]
输出：1
DP五部曲分析（与322的区别）
-
dp数组含义：
dp[i][j] 表示用前i种硬币凑出金额j的组合数（注意：是组合数，不是最少个数）
-
递推公式：
- 不选第i种硬币：
dp[i][j] = dp[i-1][j]
- 选第i种硬币：
dp[i][j] = dp[i][j-coins[i-1]]（注意是加法，不是取最小值）
- 总组合数：
dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]
-
初始化：
-
dp[0][0] = 1（0种硬币凑0元，有1种组合：不选任何硬币）
-
dp[i][0] = 1（凑0元永远只有1种组合）
-
dp[0][j>0] = 0（0种硬币无法凑正数金额）
-
遍历顺序：外层遍历硬币（保证组合不重复），内层正序遍历金额
-
打印验证：打印dp数组验证
完整版代码（二维DP）
/**
* LeetCode518. 零钱兑换 II（完全背包-组合数型）
* 时间复杂度：O(coins.length * amount)
* 空间复杂度：O(coins.length * amount)
*
* 【与322的区别】
* - 322求：最少的硬币个数（最值型）→ Math.min
* - 518求：组合数（计数型）→ 加法
*/
function change(amount, coins) {
const coinCount = coins.length;
const targetAmount = amount;
// 【易错点1】边界处理：凑0元返回1（唯一组合：不选任何硬币）
if (targetAmount === 0) return 1;
// 【步骤1】确定dp数组及下标的含义
// dp[i][j] = 用前i种硬币凑出金额j的组合数
const dp = new Array(coinCount + 1).fill(0).map(() => new Array(targetAmount + 1).fill(0));
// 【步骤3】dp数组如何初始化
// 【易错点2】凑0元的组合数是1（不选任何硬币），不是0
for (let i = 0; i <= coinCount; i++) {
dp[i][0] = 1; // 凑0元永远只有1种组合
}
// 【步骤4】确定遍历顺序：外层遍历硬币，内层正序遍历金额
// 【关键】外层遍历硬币保证了组合不重复：如[1,2]和[2,1]被视为同一种组合
for (let i = 1; i <= coinCount; i++) {
const currentCoin = coins[i - 1]; // 【易错点3】数组索引转换
for (let j = 1; j <= targetAmount; j++) {
if (j < currentCoin) {
// 金额不足，无法用当前硬币，继承前i-1种的组合数
dp[i][j] = dp[i - 1][j];
} else {
// 【步骤2】确定递推公式（组合数 = 不用 + 用）
// dp[i-1][j]：不用第i种硬币的组合数
// dp[i][j-currentCoin]：用第i种硬币的组合数（注意是dp[i]，可重复选）
dp[i][j] = dp[i - 1][j] + dp[i][j - currentCoin];
}
}
}
// 无法凑出时自然返回0（符合题目要求）
return dp[coinCount][targetAmount];
}
// 测试用例
console.log(change(5, [1, 2, 5])); // 4
console.log(change(3, [2])); // 0
console.log(change(10, [10])); // 1
console.log(change(0, [1, 2])); // 1
空间优化版（一维DP）
/**
* 空间优化版：一维DP
* 时间复杂度：O(coins.length * amount)
* 空间复杂度：O(amount)
*/
function change(amount, coins) {
const coinCount = coins.length;
const targetAmount = amount;
if (targetAmount === 0) return 1;
// 【步骤1】一维dp数组：dp[j] = 凑出金额j的组合数
const dp = new Array(targetAmount + 1).fill(0);
dp[0] = 1; // 【核心初始化】凑0元的组合数为1
// 【步骤4】遍历顺序：外层遍历硬币，内层正序遍历金额
// 【关键理解】外层遍历硬币 → 保证组合数不重复
// 如果外层遍历金额，内层遍历硬币，会得到排列数（顺序有关）
for (let i = 1; i <= coinCount; i++) {
const currentCoin = coins[i - 1];
// 【易错点4】完全背包：金额正序遍历（从currentCoin开始）
for (let j = currentCoin; j <= targetAmount; j++) {
// 【步骤2】递推公式（一维版）
// dp[j]（更新前）= 不用当前硬币的组合数（上一轮的结果）
// dp[j - currentCoin]（更新后）= 用当前硬币的组合数（当前轮已更新的结果）
dp[j] = dp[j] + dp[j - currentCoin];
}
}
return dp[targetAmount];
}
前端应用场景：
-
支付方式组合：计算用户可以用多少种不同的支付方式组合完成支付
-
资源配置方案：计算有多少种不同的资源配置方案可以达到目标
-
功能组合统计：计算有多少种不同的功能组合可以满足用户需求
-
优惠券组合：计算有多少种不同的优惠券组合可以使用
四、进阶拓展级（3道，中大厂加分，理解即可）
9. LeetCode300. 最长递增子序列
题目链接：300. 最长递增子序列
难度：中等
核心：单维度DP的经典拓展，理解「非连续状态转移」
前端场景：数据趋势分析、序列统计、时间线组件、用户行为序列分析
题目描述：
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
解释：最长递增子序列是 [0,1,2,3]，长度为 4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
解释：最长递增子序列是 [7]，长度为 1
DP五部曲分析
-
dp数组含义：
dp[i] 表示以 nums[i] 为最后一个元素的最长严格递增子序列的长度
-
递推公式：
- 对于每个
nums[i]，遍历前面所有元素 nums[j] (j < i)
- 如果
nums[i] > nums[j]，则 nums[i] 可以接在 nums[j] 的子序列后面
-
dp[i] = Math.max(dp[i], dp[j] + 1) （在所有满足条件的j中取最大值）
-
初始化：
dp[i] = 1（每个元素自身构成长度为1的子序列）
-
遍历顺序：外层遍历i（从1到n-1），内层遍历j（从0到i-1）
-
打印验证：打印dp数组，返回最大值（注意：最长子序列不一定以最后一个元素结尾）
完整版代码
/**
* LeetCode300. 最长递增子序列
* 时间复杂度：O(n²)
* 空间复杂度：O(n)
*/
function lengthOfLIS(nums) {
const count = nums.length;
// 【易错点1】边界处理：空数组/单元素数组
if (count <= 1) return count;
// 【步骤1】确定dp数组及下标的含义
// dp[i] = 以nums[i]为最后一个元素的最长严格递增子序列的长度
// 【易错点2】初始化错误：必须初始化为1，不能初始化为0
// 因为每个元素自身至少构成长度为1的子序列
const dp = new Array(count).fill(1);
// 【步骤4】确定遍历顺序：外层遍历i，内层遍历j
// 【易错点3】i从1开始：i=0时前面没有元素，无法计算
for (let i = 1; i < count; i++) {
const curNum = nums[i]; // 当前元素
// 内层遍历：检查i前面所有元素j（而非仅j=i-1）
// 【易错点4】必须遍历所有j<i，不能只遍历j=i-1
// 因为子序列可以非连续，nums[i]可以接在任意满足条件的nums[j]后面
for (let j = 0; j < i; j++) {
// 【步骤2】确定递推公式
// 【易错点5】递增条件：必须是严格递增（>），不能是>=
if (curNum > nums[j]) {
// 如果nums[i] > nums[j]，则nums[i]可以接在nums[j]的子序列后面
// 取所有满足条件的dp[j]+1的最大值
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
// 【步骤5】打印验证
// console.log(`dp[${i}] = ${dp[i]}`);
}
// 【易错点6】返回错误：不能返回dp[count-1]
// 因为最长递增子序列不一定以最后一个元素结尾
// 必须返回dp数组中的最大值
return Math.max(...dp);
}
// 测试用例
console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])); // 4
console.log(lengthOfLIS([0, 1, 0, 3, 2, 3])); // 4
console.log(lengthOfLIS([7, 7, 7, 7, 7, 7, 7])); // 1
console.log(lengthOfLIS([1, 3, 6, 7, 9, 4, 10, 5, 6])); // 6
前端应用场景：
-
时间线组件：在时间线中，找到最长连续增长的时间段
-
用户行为分析：分析用户行为序列中最长的正向发展趋势
-
数据可视化：在图表中高亮显示数据的最长递增区间
-
版本号比较：找到版本号序列中最长的递增子序列
10. LeetCode121. 买卖股票的最佳时机 ★
题目链接：121. 买卖股票的最佳时机
难度：简单
核心：DP + 贪心结合，也可纯DP实现，理解「状态定义的简化」
前端场景：数据趋势、收益计算、股票K线图分析、价格波动分析
题目描述：
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法完成, 所以返回 0。
DP五部曲分析
-
dp数组含义：
dp[i] 表示第i天卖出股票能获得的最大利润
-
递推公式：
dp[i] = prices[i] - minPrice（当天价格减去之前的最小价格）
-
初始化：
dp[0] = 0（第0天无法卖出），minPrice = prices[0]
-
遍历顺序：从左到右（i从1到n-1），同时维护最小价格
-
打印验证：打印dp数组，返回最大值（注意：最大利润不一定在最后一天卖出）
完整版代码
/**
* LeetCode121. 买卖股票的最佳时机
* 时间复杂度：O(n)
* 空间复杂度：O(n)
*/
function maxProfit(prices) {
const count = prices.length;
// 【易错点1】边界处理：空数组/单元素数组
if (count <= 1) return 0;
// 【步骤1】确定dp数组及下标的含义
// dp[i] = 第i天卖出股票能获得的最大利润
const dp = new Array(count).fill(0);
// 【步骤3】dp数组如何初始化
// 第0天无法卖出（必须先买入），利润为0
dp[0] = 0;
// 维护遍历到当前的最小价格（用于计算利润）
let minPrice = prices[0]; // 初始买入价格是第0天的价格
// 【步骤4】确定遍历顺序：从左到右
for (let i = 1; i < count; i++) {
const curPrice = prices[i]; // 当天价格
// 【核心逻辑1】更新最小价格（必须先更新，再计算利润）
// 【易错点2】顺序错误：如果先计算利润再更新minPrice，会导致"当天买当天卖"的逻辑错误
// 正确的顺序：先更新minPrice（基于之前的价格），再计算当天卖出的利润
minPrice = Math.min(minPrice, curPrice);
// 【步骤2】确定递推公式
// 第i天卖出的最大利润 = 当天价格 - 之前的最小价格（最佳买入点）
// 如果结果为负，dp[i]保持0（等价于不交易）
dp[i] = Math.max(0, curPrice - minPrice);
// 【步骤5】打印验证
// console.log(`第${i}天：价格=${curPrice}, 最小价格=${minPrice}, 利润=${dp[i]}`);
}
// 【易错点3】返回错误：不能返回dp[count-1]
// 因为最大利润不一定在最后一天卖出（如示例1中最大利润在第5天，不是最后一天）
// 必须返回dp数组中的最大值
return Math.max(...dp);
}
// 测试用例
console.log(maxProfit([7, 1, 5, 3, 6, 4])); // 5
console.log(maxProfit([7, 6, 4, 3, 1])); // 0
console.log(maxProfit([2, 4, 1])); // 2
console.log(maxProfit([3, 2, 6, 5, 0, 3])); // 4
空间优化版（只需一个变量）
/**
* 空间优化版：贪心思想
* 时间复杂度：O(n)
* 空间复杂度：O(1) ← 从O(n)优化到O(1)
*
* 【优化思路】
* 观察：dp[i]只依赖dp[i-1]和minPrice
* 而且我们只需要最大值，不需要保存整个dp数组
* 用一个变量maxProfit实时更新最大值即可
*/
function maxProfit(prices) {
const count = prices.length;
if (count <= 1) return 0;
let minPrice = prices[0]; // 最小买入价格
let maxProfit = 0; // 最大利润
for (let i = 1; i < count; i++) {
const curPrice = prices[i];
// 更新最小价格
minPrice = Math.min(minPrice, curPrice);
// 计算当天卖出的利润，并更新最大利润
maxProfit = Math.max(maxProfit, curPrice - minPrice);
}
return maxProfit;
}
前端应用场景：
-
股票K线图：在股票图表中，计算买入卖出的最佳时机和最大收益
-
价格趋势分析：分析商品价格变化，找到最佳买卖点
-
收益计算器：在投资应用中，计算投资组合的最大收益
-
数据波动分析：分析数据序列中的最大正向波动（类似股票收益）
五、总结
通过这10道动态规划经典题目，我们掌握了：
核心框架：DP五部曲
- 确定dp数组及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 打印dp数组（验证）
题目分类
| 类别 |
题目 |
核心特点 |
空间优化 |
| 基础递推 |
爬楼梯、最大子数组和、打家劫舍 |
一维DP，状态转移简单 |
滚动变量 O(1) |
| 路径型DP |
不同路径、不同路径II |
二维DP，网格问题 |
一维数组 O(n) |
| 背包问题 |
零钱兑换、零钱兑换II |
完全背包，最值/计数 |
一维数组 O(amount) |
| 序列问题 |
最长递增子序列 |
非连续状态转移 |
难优化 |
| 状态机DP |
买卖股票、打家劫舍II |
状态转换，环形问题 |
滚动变量 O(1) |
易错点总结
-
边界处理：空数组、单元素、索引转换
-
初始化：根据问题特点正确初始化（0、1、Infinity等）
-
遍历顺序：完全背包正序，01背包倒序
-
返回值：注意是返回
dp[n]还是Math.max(...dp)
-
空间优化：注意更新顺序，避免覆盖未使用的值
前端应用价值
动态规划在前端开发中广泛应用于：
-
性能优化：资源分配、组件懒加载优化
-
业务逻辑：支付找零、权限分配、任务调度
-
数据可视化：趋势分析、K线图、时间线组件
-
算法优化：路径规划、组合统计、最值计算
掌握这10道题目，足以应对前端算法面试中的大部分DP问题。记住：先理解DP五部曲框架，再套用到具体问题，最后优化空间复杂度。
相关资源：
登录
