动态规划：
如果说算法是解决问题的“套路”，那动态规划就是一种“拆解问题、巧用经验”的套路。它的核心思路可以用一句话概括：把复杂问题拆成小问题，记住小问题的答案，避免重复计算。
先看一个生活例子：算楼梯台阶
假设你要上10级台阶，每次只能走1级或2级，一共有多少种走法？
直接算10级很难，不如拆成小问题：
- 上10级的最后一步，要么是从第9级走1级，要么是从第8级走2级。
- 所以，10级的走法 = 9级的走法 + 8级的走法。
- 同理，9级的走法 = 8级的走法 + 7级的走法……
- 直到最基础的情况：1级只有1种走法，2级有两种走法（1+1或2）。
这里的关键是：后面的答案依赖前面的答案，而前面的答案可以重复利用。 我们不用每次都重新算，只要把算过的结果记下来（比如用一个数组存起来），就能一步步推导出最终答案。这就是动态规划的核心：用子问题的解推导父问题的解，并用“备忘录”保存子问题答案。
动态规划的3个核心要素
- 状态定义：
用一个“变量”描述子问题的核心。比如上面的例子中，dp[n]代表"上n级台阶的走法数"，这个dp[n]就是“状态”。
- 状态转移方程：
子问题之间的关系。比如dp[n] = dp[n-1] + dp[n-2]，就是用n-1和n-2的解推导n的解。
- 初始条件：
最基础的子问题答案。比如dp[1] = 1, dp[2] = 2,没有这些“起点”，就无法推导后面的结果。
为什么要用动态规划？
最大的好处是减少重复计算。
比如算10级台阶时，如果不用动态规划，可能会递归计算dp[9]和dp[8]，而算dp[9]时又会重复算dp[8]和dp[7]……越往后重复越多，效率越低。
动态规划通过“记录子问题答案”，让每个子问题只算一次，把时间复杂度从指数级降到线性级（比如上面的例子，从O(2ⁿ)降到O(n)）。
前端开发中的常见场景
- 路径规划：
比如网格类组件（如地图、表格）中，计算从左上角到右下角的最短路径（每次只能右移或下移），可以用动态规划拆解为“当前格子的最短路径=左边格子的路径 + 上边格子的路径”。
- 最长公共子序列：
比较两个字符串的相似性（如文本diff功能），比如“abcde”和“ace”的最长公共子序列是“ace”，可以用动态规划一步步对比字符。
- 资源分配：
比如前端性能优化中，给多个任务分配有限的时间/内存，求最大收益（类似“背包问题”），用动态规划决定每个任务分配多少资源。
- 状态记忆：
比如在表单中，记录用户每一步的输入状态，回退时直接复用之前的结果，避免重新计算（本质是用“备忘录”保存子状态）。
代码如下：
/**
* @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→1
const grid2 = [
[1, 2, 3],
[4, 5, 6]
];
console.log("网格2的最短路径和:", minPathSum(grid2)); // 输出：12，路径是 1→2→3→6
代码如下：
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（无公共子序列）
代码如下：
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
总结：
动态规划就像“走楼梯时，记住每一级台阶有几种走法，不用每次都从头数”。它通过拆解问题、记录中间结果，让复杂问题变得简单高效，是前端处理“有依赖关系的多步骤问题”的利器。