q1

动态规划（Dynamic Programming, DP）是面试中常见的一类算法问题，通常用于优化递归解法，避免重复计算。动态规划问题大多涉及到求解最优解、计数问题、组合问题等。以下是一些常见的动态规划面试题，包括问题描述、解题思路及其实现。

1. 爬楼梯问题

问题描述： 假设你正在爬楼梯。需要 n 步才能到达楼顶。每次你可以爬 1 或 2 步。计算到达楼顶的不同方法总数。

解题思路： 这个问题可以看作是斐波那契数列的变形。爬到第 n 步的方法数是爬到第 n-1 步的方法数加上爬到第 n-2 步的方法数。

function climbStairs(n) {
    if (n <= 2) return n;
    let dp = [0, 1, 2];
    for (let i = 3; i <= n; i++) {
        dp[i % 3] = dp[(i - 1) % 3] + dp[(i - 2) % 3];
    }
    return dp[n % 3];
}

2. 最大子序和

问题描述： 给定一个整数数组 nums，找出一个具有最大和的连续子数组，并返回其和。

解题思路： 使用动态规划的思想，可以通过维护一个 currentSum 来记录当前子数组的和。如果 currentSum 小于 0，则重置子数组的起始位置。

function maxSubArray(nums) {
    let maxSum = nums[0];
    let currentSum = nums[0];
    for (let i = 1; i < nums.length; i++) {
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        maxSum = Math.max(maxSum, currentSum);
    }
    return maxSum;
}

3. 最小路径和

问题描述： 给定一个 m x n 的矩阵，每个格子里有一个数字。你从左上角出发，最终到达右下角。只能向下或向右移动。求最小路径和。

解题思路： 动态规划的方法，使用 dp[i][j] 表示从左上角到达格子 (i, j) 的最小路径和。可以通过选择上方或左方格子的值来递推。

function minPathSum(grid) {
    const m = grid.length;
    const n = grid[0].length;
    let dp = Array(m).fill().map(() => Array(n).fill(0));

    dp[0][0] = grid[0][0];
    
    for (let i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][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++) {
        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];
}

4. 背包问题

问题描述： 给定一组物品，每个物品有重量和价值。给定一个背包的容量，问能装入背包的最大价值是多少？

解题思路： 经典的 0/1 背包问题，可以使用动态规划来解决。dp[i] 表示当前背包容量为 i 时的最大价值。

function knapsack(weights, values, capacity) {
    const n = weights.length;
    let dp = Array(capacity + 1).fill(0);
    
    for (let i = 0; i < n; i++) {
        for (let w = capacity; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

5. 最长公共子序列

问题描述： 给定两个字符串 s1 和 s2，找到它们的最长公共子序列的长度。

解题思路： 可以用二维动态规划来求解，dp[i][j] 表示 s1[0..i-1] 和 s2[0..j-1] 的最长公共子序列长度。

function longestCommonSubsequence(s1, s2) {
    const m = s1.length;
    const n = s2.length;
    let dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));
    
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (s1[i - 1] === s2[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];
}

6. 不同路径

问题描述： 一个机器人位于一个 m x n 网格的左上角，机器人只能向下或向右移动。问机器人有多少种不同的路径可以到达右下角。

解题思路： 动态规划法，用 dp[i][j] 表示到达位置 (i, j) 的不同路径数。可以从上方或左方移动到达当前格子。

function uniquePaths(m, n) {
    let dp = Array(m).fill().map(() => Array(n).fill(1));
    
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
}

7. 最小编辑距离

问题描述： 给定两个字符串 word1 和 word2，计算将 word1 转换为 word2 所需的最少操作次数。操作包括插入一个字符、删除一个字符或替换一个字符。

解题思路： 可以使用动态规划计算每一步的最小编辑距离。

function minDistance(word1, word2) {
    const m = word1.length;
    const n = word2.length;
    let dp = Array(m + 1).fill().map(() => 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], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
            }
        }
    }
    return dp[m][n];
}

8. 正则表达式匹配

问题描述： 实现支持 . 和 * 的正则表达式匹配，. 表示任何一个字符，* 表示零个或多个前面的字符。

解题思路： 通过动态规划进行状态转移，dp[i][j] 表示 s[0..i] 和 p[0..j] 是否匹配。

function isMatch(s, p) {
    let dp = Array(s.length + 1).fill().map(() => Array(p.length + 1).fill(false));
    dp[0][0] = true;

    for (let j = 1; j <= p.length; j++) {
        if (p[j - 1] === '*') dp[0][j] = dp[0][j - 2];
    }

    for (let i = 1; i <= s.length; i++) {
        for (let j = 1; j <= p.length; j++) {
            if (p[j - 1] === s[i - 1] || p[j - 1] === '.') {
                dp[i][j] = dp[i - 1][j - 

1];
            } else if (p[j - 1] === '*') {
                dp[i][j] = dp[i][j - 2] || (p[j - 2] === s[i - 1] || p[j - 2] === '.') && dp[i - 1][j];
            }
        }
    }
    return dp[s.length][p.length];
}

总结

动态规划是一种重要的算法设计方法，能够有效地解决一类问题，尤其是在有重叠子问题和最优子结构的情况下。面试中，掌握常见的动态规划问题，能够帮助解决大部分问题。通过对这些问题的理解和练习，能够有效提升面试能力。