动态规划完全指南 🎯

一、动态规划的核心思想 💡

1. 数学归纳思想

就像我们证明数学结论：

1. 先假设在 k < n 时结论成立
2. 然后证明 k = n 时也成立
3. 最后得出结论对所有 k 都成立

动态规划也是类似的思路：

• 假设 dp[0...i-1] 都已经计算出来了
• 思考如何用这些结果计算出 dp[i]
• 关键是设计 dp[i] 代表什么含义

2. 遍历方向

根据问题特点，我们可以选择不同的遍历方式：

正向遍历

// 从左上到右下遍历
for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
        // 计算 dp[i][j]
        dp[i][j] = someCalculation();
    }
}

反向遍历

// 从右下到左上遍历
for (let i = row - 1; i >= 0; i--) {
    for (let j = col - 1; j >= 0; j--) {
        // 计算 dp[i][j]
        dp[i][j] = someCalculation();
    }
}

斜向遍历

// 按对角线方向遍历
for (let l = 1; l <= row; l++) {
    for (let i = 0; i <= col - l; i++) {
        let j = l + i - 1;
        // 计算 dp[i][j]
        dp[i][j] = someCalculation();
    }
}

二、经典问题详解 ⭐

1. 零钱兑换问题

想象你是一个收银员，要用最少的硬币找零。

/**
 * @param {number[]} coins - 可用的硬币面额
 * @param {number} amount - 目标金额
 * @return {number} - 最少需要的硬币数
 */
const coinChange = function(coins, amount) {
    // dp[i] 表示凑出金额i需要的最少硬币数
    const dp = new Array(amount + 1).fill(Infinity);
    
    // 基础情况：凑出0元需要0个硬币
    dp[0] = 0;
    
    // 遍历每个目标金额
    for(let i = 1; i <= amount; i++) {
        // 尝试每种硬币
        for(const coin of coins) {
            if(i >= coin) {
                // 状态转移：使用当前硬币 + 剩余金额的最优解
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    
    // 如果目标金额仍然是Infinity，说明无解
    return dp[amount] === Infinity ? -1 : dp[amount];
};

2. 最长递增子序列

在股票走势图中寻找最长的上升趋势。

/**
 * @param {number[]} nums - 输入数组
 * @return {number} - 最长递增子序列的长度
 */
const lengthOfLIS = function(nums) {
    if(!nums.length) return 0;
    
    // dp[i] 表示以 nums[i] 结尾的最长递增子序列长度
    const dp = new Array(nums.length).fill(1);
    
    for(let i = 0; i < nums.length; i++) {
        // 查看之前的所有元素
        for(let j = 0; j < i; j++) {
            // 如果当前数大于之前的数，可以接在其后形成更长序列
            if(nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    
    // 返回所有位置中的最大值
    return Math.max(...dp);
};

3. 编辑距离

比如文本编辑器的自动纠错功能。

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
const minDistance = function(word1, word2) {
    const m = word1.length;
    const n = word2.length;
    
    // dp[i][j] 表示 word1 前i个字符转换到 word2 前j个字符需要的最少操作数
    const dp = Array.from(Array(m + 1), () => Array(n + 1).fill(0));
    
    // 基础情况：空字符串转换到另一个字符串
    for(let i = 0; i <= m; i++) dp[i][0] = i;
    for(let j = 0; j <= n; j++) dp[0][j] = j;
    
    for(let i = 1; i <= m; i++) {
        for(let j = 1; j <= n; j++) {
            if(word1[i-1] === word2[j-1]) {
                // 字符相同，不需要操作
                dp[i][j] = dp[i-1][j-1];
            } else {
                // 取增、删、改三种操作的最小值
                dp[i][j] = Math.min(
                    dp[i-1][j] + 1,    // 删除
                    dp[i][j-1] + 1,    // 插入
                    dp[i-1][j-1] + 1   // 替换
                );
            }
        }
    }
    
    return dp[m][n];
};

三、动态规划的常见模式 📋

1. 线性DP

• 斐波那契数列
• 最大子数组和
• 打家劫舍

2. 区间DP

• 最长回文子串
• 戳气球问题

3. 背包DP

• 0-1背包：每个物品只能用一次
• 完全背包：物品可以重复使用
• 多重背包：物品有使用次数限制

四、实战技巧总结 💪

1. 设计状态的技巧

1. 最值型问题：dp[i] 通常表示"前i个"或"以i结尾"的最优值
2. 存在型问题：dp[i] 通常表示"前i个"是否存在某种可能
3. 计数型问题：dp[i] 通常表示"前i个"的方案总数

2. 常见的状态转移类型

1. 依赖前一个状态：dp[i] = dp[i-1] + something
2. 依赖前几个状态：dp[i] = max(dp[i-1], dp[i-2], ...)
3. 依赖子问题：dp[i] = max(dp[j]) + 1, 其中j < i

五、性能优化技巧 ⚡

1. 空间优化

// 优化前：二维数组
const dp = Array.from(Array(m), () => Array(n).fill(0));

// 优化后：滚动数组
let dp = Array(n).fill(0);
let newDp = Array(n).fill(0);

2. 状态压缩

// 优化前：使用数组存储所有状态
const dp = Array(n).fill(0);

// 优化后：只存储需要的状态
let prev = 0, curr = 0;

六、调试技巧 🔍

1. 打印DP表

function debugDP(dp) {
    console.table(dp); // 使用table格式化输出
}

2. 状态转移可视化

function visualizeDP(dp, i, j) {
    console.log(`当前状态: dp[${i}][${j}] = ${dp[i][j]}`);
    console.log(`依赖状态: dp[${i-1}][${j-1}] = ${dp[i-1][j-1]}`);
}

七、练习推荐 📝

入门题目

1. LeetCode 70: 爬楼梯
2. LeetCode 53: 最大子数组和

进阶题目

1. LeetCode 322: 零钱兑换
2. LeetCode 300: 最长递增子序列

高级题目

1. LeetCode 10: 正则表达式匹配
2. LeetCode 72: 编辑距离

八、扩展阅读 📚

• 动态规划设计方法
• 前端算法优化实践
• DP vs 贪心算法