面试题：JavaScript 算法优化之动态规划应用

动态规划算法解决问题：
- 定义状态：设 dp[i][j] 表示从左上角 (0, 0) 到达位置 (i, j) 能收集到的最大得分。
- 初始化：dp[0][0] = matrix[0][0]，因为从左上角出发，初始得分就是左上角单元格的得分。
- 状态转移方程：
  - 对于 i > 0 且 j == 0 的情况（第一列），dp[i][0] = dp[i - 1][0] + matrix[i][0]，只能从上方到达。
  - 对于 i == 0 且 j > 0 的情况（第一行），dp[0][j] = dp[0][j - 1] + matrix[0][j]，只能从左方到达。
  - 对于 i > 0 且 j > 0 的情况，dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j]，取上方和左方的最大值加上当前位置的得分。
- 最终结果：dp[m - 1][n - 1] 即为从左上角到达右下角能收集到的最大得分。
- 代码实现（JavaScript）：

function maxScore(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    const dp = new Array(m).fill(0).map(() => new Array(n).fill(0));
    dp[0][0] = matrix[0][0];
    for (let i = 1; i < m; i++) {
        dp[i][0] = dp[i - 1][0] + matrix[i][0];
    }
    for (let j = 1; j < n; j++) {
        dp[0][j] = dp[0][j - 1] + matrix[0][j];
    }
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j];
        }
    }
    return dp[m - 1][n - 1];
}

空间优化将空间复杂度从 O(m * n) 降低到 O(n)：
- 观察状态转移方程 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j]，可以发现 dp[i][j] 只依赖于 dp[i - 1][j]（上一行同一列）和 dp[i][j - 1]（当前行前一列）。
- 因此，可以使用一个一维数组 dp 来代替二维数组，每次更新 dp[j] 时，dp[j - 1] 是当前行前一列的最新值，而 prev 变量保存上一行同一列的 dp 值。
- 代码实现（JavaScript）：

function maxScoreOptimized(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    const dp = new Array(n).fill(0);
    dp[0] = matrix[0][0];
    for (let j = 1; j < n; j++) {
        dp[j] = dp[j - 1] + matrix[0][j];
    }
    for (let i = 1; i < m; i++) {
        let prev = dp[0];
        dp[0] = prev + matrix[i][0];
        for (let j = 1; j < n; j++) {
            let temp = dp[j];
            dp[j] = Math.max(prev, dp[j - 1]) + matrix[i][j];
            prev = temp;
        }
    }
    return dp[n - 1];
}

优化后算法的时间复杂度：
- 优化后算法仍然有两层嵌套循环，外层循环遍历 m 行，内层循环遍历 n 列。
- 每次循环的操作时间复杂度为常数级。
- 所以优化后算法的时间复杂度仍然是 O(m * n)。

面试题：JavaScript 算法优化之动态规划应用

知识考点

面试题答案