• 《剑指 Offer （第 2 版）》动态规划部分 JavaScript 题解

  ---

  《剑指 Offer （第 2 版）》动态规划部分 JavaScript 题解

  • 《剑指 Offer （第 2 版）》动态规划部分 JavaScript 题解
  • • 10- I. 斐波那契数列
    • 10- II. 青蛙跳台阶问题
    • 42. 连续子数组的最大和
    • 14- I. 剪绳子
    • 14- II. 剪绳子 II
    • 46. 把数字翻译成字符串
    • 47. 礼物的最大价值
    • 49. 丑数
    • 60. 63. 股票的最大利润

  《剑指 Offer （第 2 版）》动态规划部分 JavaScript 题解

  《剑指 Offer（第 2 版）》通行全球的程序员经典面试秘籍。剖析典型的编程面试题，系统整理基础知识、代码质量、解题思路、优化效率和综合能力这 5 个面试要点。

  最近，把动态规划部分的题刷完了。本文来分享下这些题的解法

  10- I. 斐波那契数列

  写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

  F(0) = 0,   F(1) = 1
  F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
  1
  2

  斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
  答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

  示例 1：

  输入：n = 2 
  输出：1 
  1
  2

  示例 2：

  输入：n = 5 
  输出：5 
  1
  2

  提示：

  • 0 <= n <= 100

  力扣链接：https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof

  解题思路
  动态规划解析：

  • 状态定义： 设 dp 为一维数组，其中 dp[i] 的值代表 斐波那契数列第 i 个数字 。
  • 转移方程： dp[i + 1] = dp[i] + dp[i - 1]，即对应数列定义 f(n+1)=f(n)+f(n−1) ；
  • 初始状态： dp[0]=0, dp[1] = 1，即初始化前两个数字；
  • 返回值： dp[n] ，即斐波那契数列的第 n 个数字。

  空间复杂度优化：

  • 由于 dp 列表第 i 项只与第 i−1 和第 i−2 项有关，因此只需要初始化三个整形变量 r, a, b ，利用辅助变量 r 使 a, b 两数字交替前进即可 （具体实现见代码）。
  • 节省了 dp 列表空间，因此空间复杂度降至 O(1) 。

  /**
   * @param {number} n
   * @return {number}
   */
  var fib = function(n) {
    const MOD = 1000000007;
    let [a, b, r] = [0, 0, 1];
    if (n < 2) return n;
    for(let i = 2; i <= n; i++) {
      a = b;
      b = r;
      r = (a + b) % MOD;
    }
    return r;
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15

  10- II. 青蛙跳台阶问题

  一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
  答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

  示例 1：

  输入：n = 2
  输出：2
  1
  2

  示例 2：

  输入：n = 7
  输出：21
  1
  2

  示例 3：

  输入：n = 0
  输出：1
  1
  2

  提示：

  • 0 <= n <= 100

  力扣链接：https://leetcode.cn/problems/qing-wa-tiao-tai-jie-wen-ti-lcof

  解题思路
  设跳上 n 级台阶有 f(n) 种跳法。在所有跳法中，青蛙的最后一步只有两种情况： 跳上 1 级或 2 级台阶。

  • 当为 1 级台阶： 剩 n−1 个台阶，此情况共有 f(n−1) 种跳法；
  • 当为 2 级台阶： 剩 n−2 个台阶，此情况共有 f(n−2) 种跳法。

  f(n) 为以上两种情况之和，即 f(n)=f(n−1)+f(n−2) ，以上递推性质为斐波那契数列。

  动态规划解析：

  • 状态定义： 设 dp 为一维数组，其中 dp[i] 的值代表斐波那契数列第 i 个数字 。
  • 转移方程： dp[i+1]=dp[i]+dp[i−1] ，即对应数列定义 f(n+1)=f(n)+f(n−1) ；
  • 初始状态： dp[0]=1, dp[1]=1 ，即初始化前两个数字；
  • 返回值： dp[n] ，即斐波那契数列的第 n 个数字。

  空间复杂度优化：

  • 由于 dp 列表第 i 项只与第 i−1 和第 i−2 项有关，因此只需要初始化三个整形变量 r, a, b ，利用辅助变量 r 使 a, b 两数字交替前进即可 （具体实现见代码） 。
  • 因为节省了 dp 列表空间，因此空间复杂度降至 O(1) 。

  /**
   * @param {number} n
   * @return {number}
   */
  var numWays = function(n) {
    if (n < 2) return 1;
    const MOD = 1000000007;
    let [a, b, r] = [1, 1, 2];
  
    for(let i = 2; i <= n; i++) {
      r = (a + b) % MOD;
      a = b;
      b = r;
    }
    return r;
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16

  42. 连续子数组的最大和

  输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
  要求时间复杂度为O(n)。

  示例1:

  输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
  输出: 6
  解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
  1
  2
  3

  提示：

  • 1 <= arr.length <= 10^5
  • -100 <= arr[i] <= 100

  力扣链接：https://leetcode.cn/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof

  解题思路
  动态规划解析：

  • 状态定义： 设动态规划列表 dp ，dp[i] 代表以元素 nums[i] 为结尾的连续子数组最大和。
    • 为何定义最大和 dp[i] 中必须包含元素 nums[i] ：保证 dp[i] 递推到 dp[i+1] 的正确性；如果不包含 nums[i] ，递推时则不满足题目的连续子数组要求。
  • 转移方程： dp[i] = max{ dp[i-1]+nums[i], nums[i] }
  • 初始状态： dp[0] = nums[0]，即以 nums[0] 结尾的连续子数组最大和为 nums[0] 。
  • 返回值： 返回 dp 列表中的最大值，代表全局最大值。

  空间复杂度优化：

  • 考虑到 dp[i] 只和 dp[i-1] 相关，于是我们可以只用一个变量 pre 来维护对于当前 dp[i] 的 dp[i-1] 的值是多少。
  • 因为节省了 dp 列表空间，因此空间复杂度降至 O(1) 。

  /**
   * @param {number[]} nums
   * @return {number}
   */
  var maxSubArray = function(nums) {
    let pre = 0, maxAns = nums[0];
      nums.forEach((x) => {
          pre = Math.max(pre + x, x);
          maxAns = Math.max(maxAns, pre);
      });
      return maxAns;
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12

  14- I. 剪绳子

  给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

  示例 1：

  输入: 2
  输出: 1
  解释: 2 = 1 + 1, 1 × 1 = 1
  1
  2
  3

  示例 2:

  输入: 10
  输出: 36
  解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
  1
  2
  3

  提示：

  • 2 <= n <= 58

  解题思路
  动态规划解析：

  • 状态定义： 设动态规划列表 dp ，dp[i] 代表将长度为 i 的绳子剪成至少两段绳子之后，这些绳子长度的最大乘积。
  • 转移方程：当 i ≥ 2 时，假设对长度为 i 绳子剪出的第一段绳子长度是 j（1≤j
  • 将 i 剪成 j 和 i-j 长度的绳子，且 i−j 不再继续剪，此时的乘积是 j×(i−j) 。
  • 将 i 剪成 j 和 i−j 长度的绳子，且 i−j 继续剪成多段长度的绳子，此时的乘积是 j×dp[i−j] 。
  • 因此，当 j 固定时，有 dp[i]=max(j×(i−j),j×dp[i−j])。由于 j 的取值范围是 1 到 i ，需要遍历所有的 j 得到dp[i]的。
• 初始状态： dp[2] = 1，即长度为 2 的绳子剪成至少两段绳子之后，这些绳子长度的最大乘积为 1。
• 返回值： 最终得到 dp[n] 的值即为将长度为 n 的绳子拆分成至少两段绳子之后，这些绳子长度的最大乘积。

/**
 * @param {number} n
 * @return {number}
 */
var cuttingRope = function(n) {
  const dp = Array(n + 1).fill(0);
  dp[2] = 1;
  for(let i = 3; i <= n; i++) {
    for(let j = 2; j < i; j++) {
      dp[i] = Math.max(dp[i], dp[j] * (i - j), j * (i - j));
    }
  }
  return dp[n];
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

14- II. 剪绳子 II

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]*k[1]*...*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
1
2
3

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
1
2
3

提示：

• 2 <= n <= 1000

力扣链接：https://leetcode.cn/problems/jian-sheng-zi-ii-lcof

解题思路
在14-1的基础上，使用 BigInt 完成大数计算。因为 Math.max 不能求 BigInt 类型的最值，所以我们要自己写一个 max 函数判断最值。

/**
 * @param {number} n
 * @return {number}
 */
var cuttingRope = function (n) {

  const max = (...args) => args.reduce((prev, curr) => prev > curr ? prev : curr);

    let dp = new Array(n + 1).fill(BigInt(1));
    for (let i = 3; i <= n; i++) {
        for (let j = 2; j < i; j++) {
            dp[i] = max(dp[i], dp[j] * BigInt((i - j)), BigInt(j* (i - j)));
        }
    }
    return dp[n] % (1000000007n);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

46. 把数字翻译成字符串

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

示例 1:

输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
1
2
3

提示：

• 0 <= num < 2^31

力扣链接：https://leetcode.cn/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof

解题思路
动态规划解析：

• 状态定义： 设动态规划列表 dp ，dp[i] 代表以 数字 num 第 i 位数字 为结尾的数字的翻译方案数量。
• 转移方程：若 **数字 num 第 i 位数字 和 数字 num 第 i-1 位数字 **组成的两位数字可以被翻译，则 dp[i] = dp[i - 1] + dp[i - 2] ；否则 dp[i] = dp[i - 1]。
  • 可被翻译的两位数区间：[10, 25]。
• 初始状态： dp[0] = dp[1] = 1，即 “无数字” 和 “第 1 位数字” 的翻译方法数量均为 1 。
• 返回值： dp[n]，即此数字的翻译方案数量。

空间复杂度优化：

• 由于 dp[i] 只与 dp[i−1] 有关，因此可使用两个变量 a, b 分别记录 dp[i], dp[i - 1]，两变量交替前进即可。
• 因为节省了 dp 列表空间，因此空间复杂度降至 O(1) 。

/**
 * @param {number} num
 * @return {number}
 */
var translateNum = function(num) {
  const str = String(num);
  const { length } = str;
  let [a, b] = [1, 1];
  for(let i = 1; i < length; i++) {
    const tmp = parseInt(str.charAt(i - 1) + str.charAt(i));
    const c = tmp >= 10 && tmp <= 25 ? a + b : a;
    b = a;
    a = c;
  }
  return a;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

47. 礼物的最大价值

在一个 m * n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

示例 1:

输入: 
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
1
2
3
4
5
6
7
8

提示：

• 0 < grid.length <= 200
• 0 < grid[0].length <= 200

力扣链接：https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof

解题思路
动态规划解析：

• 状态定义： 设动态规划矩阵 dp ，dp(i, j) 代表从棋盘的左上角开始，到达单元格 (i, j) 时能拿到礼物的最大累计价值。
• 转移方程：分为以下四种情况：
  1. 当 i = 0 且 j = 0 时，为起始元素；
  2. 当 i = 0 且 j !=0 时，为矩阵第一行元素，只可从左边到达：dp[i][j] = grid[i][j] + grid[i][j - 1]
  3. 当 i != 0 且 j =0 时，为矩阵第一列元素，只可从上边到达：dp[i][j] = grid[i][j] + grid[i - 1][j]
  4. 当 i != 0 且 j !=0 时，可从左边或上边到达：dp[i][j] = grid[i][j] + Math.max(grid[i][j - 1], grid[i - 1][j])
• 初始状态： dp[0][0]=grid[0][0] ，即到达单元格 (0, 0) 时能拿到礼物的最大累计价值为 grid[0][0]。
• 返回值： dp[_m_−1][_n_−1] ，m, n 分别为矩阵的行高和列宽，即返回 dp 矩阵右下角元素。

空间复杂度优化：

• 由于 dp[i][j] 只与 dp[i-1][j] , dp[i][j-1] , grid[i][j] 有关系，因此可以将原矩阵 grid 用作 dp 矩阵，即直接在 grid 上修改即可。
• 应用此方法可省去 dp 矩阵使用的额外空间，因此空间复杂度从 O(MN) 降至 O(1)。

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxValue = function(grid) {
  const m = grid.length;
  const n = grid[0].length;
  for(let i = 0; i < m; i++) {
    for(let j = 0; j < n; j++) {
      if (i === 0 && j ===0) continue;
      else if (i === 0) grid[i][j] += grid[i][j - 1];
      else if (j === 0) grid[i][j] += grid[i - 1][j];
      else grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);
    }
  }
  return grid[m - 1][n - 1];
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

49. 丑数

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
1
2
3

**说明: **

1. 1 是丑数。
2. n 不超过1690。

力扣链接：https://leetcode.cn/problems/chou-shu-lcof

解题思路
动态规划解析：

• 状态定义： 设动态规划列表 dp ，dp[i] 代表第 i 个丑数。
• 转移方程：每轮计算 dp[i] 后，需要更新索引 p2, p3, p5 的值，使其始终满足方程条件。实现方法：分别独立判断 dp[i] 和 dp[p2]×2 , dp[p3]×3 , dp[p5]×5 的大小关系，若相等则将对应索引 p2, p3, p5 加 1 ；则 dp[i]=min{ dp[p2]×2, dp[p3]×3, dp[p5]×5 }
• 初始状态： dp[1]=1 ，即第一个丑数为 1 。
• 返回值： dp[n] ，即返回第 n 个丑数。

/**
 * @param {number} n
 * @return {number}
 */
var nthUglyNumber = function(n) {
const dp = new Array(n + 1).fill(0);
  dp[1] = 1;
  let p2 = 1, p3 = 1, p5 = 1;
  for (let i = 2; i <= n; i++) {
    const num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
    dp[i] = Math.min(Math.min(num2, num3), num5);
    if (dp[i] === num2) {
      p2++;
    }
    if (dp[i] === num3) {
      p3++;
    }
    if (dp[i] === num5) {
      p5++;
    }
  }
  return dp[n];
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

60. 63. 股票的最大利润

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
1
2
3
4

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
1
2
3

限制：

• 0 <= 数组长度 <= 10^5

力扣链接：https://leetcode.cn/problems/gu-piao-de-zui-da-li-run-lcof

解题思路
动态规划解析：

• 状态定义： 设动态规划列表 dp ，dp[i] 代表以 prices[i] 为结尾的子数组的最大利润（以下简称为 前 i 日的最大利润 ）。
• 转移方程：由于题目限定 “买卖该股票一次” ，因此前 i 日最大利润 dp[i] 等于前 i - 1 日最大利润 dp[i-1] 和第 i 日卖出的最大利润中的最大值。
• 初始状态： dp[0] = 0 ，即首日利润为 0 。
• 返回值： dp[_n_−1] ，其中 n 为 dp 列表长度。

效率优化：

• 时间复杂度降低： 在遍历 prices 时，可以借助一个变量（记为成本 cost ）每日更新最低价格。
• 可使用一个变量（记为利润 profit）代替 dp 列表。优化后的转移方程为：profit=max{ profit, prices[i]−min{ cost, prices[i] } }

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
  let [cost, profit] = [Infinity, 0];
  for(const price of prices) {
    cost = Math.min(cost, price);
    profit = Math.max(profit, price - cost);
  }
  return profit;
};
1
2
3
4
5
6
7
8
9
10
11
12