2.动态规划（Dynamic Programming）

认识

动态规划是一种解决复杂问题的算法设计范式，它通过将问题分解为相互重叠的子问题，并存储子问题的解（避免重复计算），从而高效地解决原问题。动态规划特别适合解决具有最优子结构性质和重叠子问题的问题。

其实就是将一个问题分解成相互重叠的子问题，通过反复求解子问题，来解决原来的问题

特别适合解决具有最优子结构和重叠子问题的问题。

应用场景

场景一：斐波那契数列

• 定义子问题：F(n) = F(n - 1) + F(n - 2)
• 反复执行：从2循环到n，执行上述公式

动态规划和分而治之区别？

• 区别在于子问题是否独立
• 动态规划的子问题是重叠的
• 分而治之的子问题是独立的

leetcode

+ [70.爬楼梯](https://link.juejin.cn?target=https%3A%2F%2Fleetcode-cn.com%2Fproblems%2Fclimbing-stairs%2F)
+ [198.打家劫舍](https://link.juejin.cn?target=https%3A%2F%2Fleetcode-cn.com%2Fproblems%2Fhouse-robber%2F)

核心思想

1. 最优子结构：问题的最优解包含其子问题的最优解
2. 重叠子问题：子问题会被多次重复计算
3. 记忆化存储：存储已计算的子问题解，避免重复计算

动态规划与分治的区别

• 分治：问题分解为独立子问题，子问题不重叠
• 动态规划：问题分解为重叠子问题，子问题之间有依赖关系

JavaScript中实现动态规划需要注意

1. 合理定义状态和状态转移方程
2. 选择合适的实现方式（自顶向下或自底向上）
3. 注意空间复杂度的优化
4. 处理边界条件和初始状态
5. 必要时进行回溯以获取具体解

动态规划的原理

动态规划的实现通常有两种方式：

1. 自顶向下（Memoization）
   • 使用递归
   • 用一个表（通常是数组或对象）存储子问题的解
   • 遇到子问题时，先查表，如果未计算则计算并存储
2. 自底向上（Tabulation）
   • 使用迭代
   • 从最小的子问题开始，逐步构建更大问题的解
   • 通常使用表格存储中间结果

基本步骤

1. 定义状态：确定如何表示子问题
2. 找出状态转移方程：描述子问题之间的关系
3. 确定初始状态：确定最小子问题的解
4. 确定计算顺序：确保在计算大问题时，所需的小问题已经解决
5. 优化空间复杂度：考虑是否可以优化空间使用

JavaScript中的动态规划应用

1. 斐波那契数列

自顶向下实现（Memoization）：

function fibonacci(n, memo = {}) {
    // 基本情况
    if (n <= 1) return n;
    
    // 检查是否已经计算过
    if (memo[n]) return memo[n];
    
    // 计算并存储结果
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
    return memo[n];
}

console.log(fibonacci(10)); // 输出: 55
console.log(fibonacci(50)); // 输出: 12586269025

自底向上实现（Tabulation）：

function fibonacci(n) {
    // 创建表格存储子问题解
    const dp = new Array(n + 1);
    
    // 初始状态
    dp[0] = 0;
    dp[1] = 1;
    
    // 从小到大计算
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}

console.log(fibonacci(10)); // 输出: 55
console.log(fibonacci(50)); // 输出: 12586269025

2. 最长公共子序列（LCS）

function longestCommonSubsequence(text1, text2) {
    const m = text1.length;
    const n = text2.length;
    
    // 创建DP表
    const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
    
    // 填充DP表
    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]);
            }
        }
    }
    
    // 回溯构建LCS
    let i = m, j = n;
    const lcs = [];
    
    while (i > 0 && j > 0) {
        if (text1[i - 1] === text2[j - 1]) {
            lcs.unshift(text1[i - 1]);
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }
    
    return {
        length: dp[m][n],
        sequence: lcs.join('')
    };
}

// 使用示例
const result = longestCommonSubsequence("ABCBDAB", "BDCABA");
console.log(result.length);      // 输出: 4
console.log(result.sequence);    // 输出: "BCBA" 或 "BDAB"

3. 0/1背包问题

function knapsack(weights, values, capacity) {
    const n = weights.length;
    
    // 创建DP表
    const dp = Array.from({ length: n + 1 }, () => Array(capacity + 1).fill(0));
    
    // 填充DP表
    for (let i = 1; i <= n; i++) {
        for (let w = 1; w <= capacity; w++) {
            if (weights[i - 1] <= w) {
                dp[i][w] = Math.max(
                    values[i - 1] + dp[i - 1][w - weights[i - 1]],
                    dp[i - 1][w]
                );
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    
    // 回溯找出选择的物品
    let w = capacity;
    const selectedItems = [];
    
    for (let i = n; i > 0 && w > 0; i--) {
        if (dp[i][w] !== dp[i - 1][w]) {
            selectedItems.push(i - 1);
            w -= weights[i - 1];
        }
    }
    
    return {
        maxValue: dp[n][capacity],
        selectedItems: selectedItems.reverse()
    };
}

// 使用示例
const weights = [1, 3, 4, 5];
const values = [1, 4, 5, 7];
const capacity = 7;

const result = knapsack(weights, values, capacity);
console.log(result.maxValue);        // 输出: 9
console.log(result.selectedItems);   // 输出: [1, 2] (表示选择第2和第3个物品)

4. 最小路径和

function minPathSum(grid) {
    const m = grid.length;
    const n = grid[0].length;
    
    // 创建DP表
    const dp = Array.from({ length: m }, () => Array(n).fill(0));
    
    // 初始状态
    dp[0][0] = grid[0][0];
    
    // 填充第一行
    for (let j = 1; j < n; j++) {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }
    
    // 填充第一列
    for (let i = 1; i < m; i++) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    
    // 填充剩余部分
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        }
    }
    
    return dp[m - 1][n - 1];
}

// 使用示例
const grid = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1]
];
console.log(minPathSum(grid)); // 输出: 7 (路径是 1→3→1→1→1)

动态规划的优化技巧

1. 空间优化：
   • 对于只依赖前一行/一列的状态，可以滚动数组优化
   • 例如背包问题可以优化到一维数组
2. 状态压缩：
   • 减少状态维度
   • 使用位运算等技巧压缩状态表示
3. 预处理：
   • 对输入数据进行预处理，减少计算量
   • 例如前缀和、差分数组等
4. 记忆化搜索：
   • 对于状态空间稀疏的问题，使用对象或Map代替数组

动态规划的适用场景

1. 最优化问题：如最大值、最小值、最长、最短等
2. 计数问题：如计数问题、组合问题等
3. 判断问题：如可行性判断、存在性问题等
4. 博弈问题：如两人轮流取物品等

动态规划的设计模式

1. 线性DP：处理线性结构的问题，如数组、字符串
2. 区间DP：处理区间相关的问题，如矩阵链乘法
3. 树形DP：处理树形结构的问题，如树上的最大独立集
4. 状压DP：处理状态压缩的问题，如旅行商问题
5. 数位DP：处理与数字相关的问题，如数位统计