动态规划

使用递归去解决问题虽然代码简洁、简单，但是效率不高。很多用递归解决的算法题，如果用动态规范来解决，效率会更高。

动态规划(dynamic programming )是通过组合子问题的解决，从而解决整个问题的算法。英文中的 programming，指的是一种规划，而不是计算机代码。

动态规划适用于子问题不是独立的情况，对每个子问题只求解一次，使用数组来建立一张表格，来存放被分解成众多子问题的解，从而避免重复计算相同的子问题。

本章节分为 3 个部分：

• Part 1
  • 最大子序和
  • 爬楼梯
  • 买卖股票的最佳时机
• Part 2
  • 打家劫舍
  • 零钱兑换
  • 跳跃游戏
• Part 3
  • 不同路径
  • Longest Increasing Subsequence
  • 单词拆分

阅读完本章节，你将对动态规划算法有更加熟悉对了解。

最大子序和、爬楼梯和买卖股票的最佳时机

最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例

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

暴力破解

思路

从数组最左边开始于数组右边数据依次相加，将相加之后数据进行比较，比较之后最大值为最终结果

详解

1. 创建临时变量 sum 和最大值 maxNumber
2. 从数组子序列左端开始遍历依次取数据
3. 从数组子序列右端开始遍历依次取数据和数组左边数据依次相加
4. 将相加之后值与最大值 sum 进行比较，大的值赋值与 maxNumber
5. 最终获得最大值

/**
 * @param {number[]} nums
 * @return {number}
 */
const maxSubArray = function (nums) {
  let sum = 0;
  let maxNumber = 0;

  for (let i = 0; i < nums.length; i++) { // 从数组子序列左端开始
    for (let j = i; j < nums.length; j++) { // 从数组子序列右端开始
      sum = 0;
      for (let k = i; k <= j; k++) { // 暴力计算
        sum += nums[k];
      }
      if (sum > maxNumber) {
        maxNumber = sum;
      }
    }
  }
  return maxNumber;
};

复杂度分析

• 时间复杂度：O(n^3)O(n3) 对于每个元素，通过三次遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n^3)O(n3) 的时间。
• 空间复杂度：O(1)O(1)

方法二 动态规划法

思路

数组从左端开始依次和右端数据相加，两数之和为最大数 sum 。下一次相加之后和最大数进行比较，较大数赋值与 sum 由于有负数存在，如果两数相加之后为负数，则两数之和后的最大数为上一个数。

详解

1. 从数组获取第一个值为最大值 sum 和中间值 n
2. 遍历数组，如果中间值n大于0,则和中间值相加，相加结果和最大值比较，较大值赋值与 sum
3. 如果中间值小于0，则将当前值作为中间值

/**
 * @param {number[]} nums
 * @return {number}
 */
const maxSubArray = function (nums) {
  let sum = nums[0];
  let n = nums[0];
  for (let i = 1; i < nums.length; i++) {
    if (n > 0) n += nums[i]; // 判断中间值是否大于0
    else n = nums[i];
    if (sum < n) sum = n; // 相加后的值和最大值作比较
  }
  return sum;
};

复杂度分析

• 时间复杂度：O(n)O(n)

  对于每个元素，通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n)O(n) 的时间。

• 空间复杂度：O(1)O(1)

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例一

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例二

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

方法一 递归法

思路

1. 假设现在输入 nn = 10，记作 f(n)f(n)，那么 10 个台阶 = 9 个台阶 + 走 1 步，此处记作 f(n-1)f(n−1)，也可以是 10 个台阶 = 8 个台阶 + 走 2 步，记作 f(n-2)f(n−2)
2. 步骤 1 的 f(n-1)f(n−1) ：9 个台阶 = 8 个台阶 + 走 1 步，也可以是 9 个台阶 = 7 个台阶 + 走 2 步
3. 步骤 1 的 f(n-2)f(n−2)：8 个台阶 = 7 个台阶 + 走 1 步，也可以是 8 个台阶 = 6 个台阶 + 走 2 步
4. 以此类推，可以得出递归函数：f(n) = f(n-1) + f(n-2)f(n)=f(n−1)+f(n−2)

详解

从上述思路得出的"递归函数一"如下所示，但是由于执行效率低下，需要进行算法优化。 通常情况下，我们提高执行速度的方式是用"空间换取时间"，顾名思义，占用更多的内存来减少计算时间，请看"递归函数二"： 1. 申请一个Object用于存放已经计算过的楼梯 map[n]=nummap[n]=num 2. 每次函数执行前，先判断当前楼层是否已经被计算过，是，则直接从 map 中获得结果；否，则进入计算，并在 map 中记录计算结果

代码

// 递归函数一
const climbStairs = function (n) {
  if (n <= 2) {
    return n;
  } else {
    return climbStairs(n - 1) + climbStairs(n - 2);
  }
};

// 递归函数二
const fn = (n, map) => {
    if(n <= 2) {
      return n
    }
    const result = map[n];
    if(result) {
        return result;
    } else {
      let num = fn(n - 1, map) + fn(n - 2, map);
      map[n] = num;
      return num
    }
}

/**
 * @param {number} n
 * @return {number}
 */
const climbStairs = (n) => {
    const map = {};
    return fn(n, map) 
};

• 时间复杂度：O(2^n)O(2n)
  • 递归函数一，由于每个节点都需要计算，则时间复杂度就等于二叉树的节点数(2^n-1)(2n−1)
  • 经过递归函数二的优化以后，避免了重复的运算，时间复杂度也就变成了二叉树的高度：O(n)O(n)
• 空间复杂：O(n)O(n)

方法二 动态规划

思路

我们先从给的示例入手，示例中说到： 2个台阶有2种方法，3个台阶有3种方法，那么以此基础。4个台阶：3个台阶走一步或者2个台阶走2步，可以算出 4 个台阶有 3 + 2 = 5 种方法。5个台阶：4个台阶走一步或者3个台阶走2步，也就是 5 + 3 = 8 种方法。以此类推，我们可以发现，这就是经典的斐波那切数列：f(n)=f(n-1)+f(n-2)f(n)=f(n−1)+f(n−2)

详解

1. 申明变量 resultresult，记录一些已知结果，比方说：1 个台阶 1 种解法，2 个台阶 2 种解法
2. 为了方便根据数组下标进行查找，在 result 中加一个 0 占位：result = [0, 1, 2]result=[0,1,2];
3. 当输入 n 大于等于 3 时，开始循环计算并记录结果： result[i] = result[i - 1] + result[i - 2]result[i]=result[i−1]+result[i−2];
4. 循环结束后，输出 resultresult 下标为 nn 的结果。

代码

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

复杂度分析

• 时间复杂度：O(n)O(n)

  对 n 进行了一次循环遍历，运行次数与输入 nn 成正比

• 空间复杂度：O(n)O(n)

  创建了一个长度为 nn 的空间，空间复杂度是 O(n)O(n)

买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。 注意你不能在买入股票前卖出股票。

示例 1:

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

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

方法一 穷举法

思路

首先，我们想到直观解法，即计算出第 i 天买入，后续所有可能卖出情况下的收益，取最大值即为第 i 天买入可获得的最大收益。

然后比较每一天的最大收益，取最大值，即可得出所有操作中能获取的最大收益。

详解

假设第 i 天当天买入，依次遍历第 i 天之后的所有可能卖出的情况，比较得出收益中的最大值 max。 假设 maxProfit 为当前可以获得的最大收益，初始值为 0，将第 i 天买入收益最大值 max 与 maxProfit 比较，如果 max > maxProfit 则更新 maxProfit 的值，依次进行，最终得到最大收益。

代码

/**
 * @param {number[]} prices
 * @return {number}
 */
function maxProfit(prices) {
  let maxProfit = 0;

  function getMax(i) { // 获取第 i 天后股票价格中的最大值
    let max = prices[i + 1];

    for (let j = i + 1; j < prices.length; j++) {
      if (prices[j] > max) {
        max = prices[j];
      }
    }

    return max;
  }

  for (i = 0; i < prices.length - 1; i++) {
    const max = getMax(i) - prices[i]; // 记录第 i 天买入后续合理时间卖出可获得的最大收益
    maxProfit = Math.max(maxProfit, max); // 比较当前已经获取到的最大收益与当天最大收益，取较大者
  }

  return maxProfit;
};

复杂度分析

• 时间复杂度：O(n^2) O(n2)

  我们使用了双重循环计算，内层循环求第 i 天买入后的日子里股票的最高价格，外层循环比较计算最大收益 maxProfit。 那么第一天需要比较 n - 1n−1 次才能求出后续最大价格，第二天比较 n - 2n−2 次，以此类推… 根据等差数列求和公式，最后比较的总次数为 n * (n - 1) / 2n∗(n−1)/2 ，所以最终得出时间复杂度为 O(n^2)O(n2)。

• 空间复杂度：O(n) O(n)

使用长度为 nn 的额外数组保存每日可获得的最大收益，即空间复杂度为 O(n)O(n)

方法二 求最大差值

思路

再次理解题意，每一天的股票价格组成一个数组，本质上我们只需要寻找一个数组中下标大的数值减去下标小的数值的最大差值即可，而这个差值即为最大收益。

详解

我们先假设最大利润为 maxProfit 和最小成本为 minPrice，令 minPrice 为数组中第一个元素，然后开始遍历数组。

当遍历到某一元素 prices[i] 时： 1. 如果 prices[i] 小于 minPrice，将 prices[i] 的值赋给 minPrice 2. 否则比较 prices[i] - minPrice（此时为非负数）与 maxProfit 的大小 3. 若 prices[i] - minPrice 的值大于 maxProfit，则把新的最大收益值赋给 maxProfit，否则不予处理

最终遍历一次，即可获得最大利润 maxProfit。

代码

function maxProfit(prices) {
  let minPrice = 0;
  let maxProfit = 0;

  prices.forEach((price, index) => {
    if (index === 0) { // 初始化最小价格为第一个元素
      minPrice = price;
    } else if (price < minPrice) { // 遍历过程中发现最小价格，则重新赋值
      minPrice = price;
    } else if (price - minPrice > maxProfit) { // 比较当日卖出收益与当前已获取的最大收益
      maxProfit = price - minPrice;
    }
  });

  return maxProfit;
};

复杂度分析

• 时间复杂度：O(n) O(n)
• 空间复杂度：O(1)O(1)

在算法中，我们使用两个公共变量保存最大收益以及最小卖出价格，所以空间复杂度为常数级。

解法三 动态规划

思路

有了解法二的参考，我们还可以利用差分数组连续求和来得出最大收益。第 i 天买入股票，第 i + 1 天卖出，那么我们可以获得的收益为第二天价格与第一天价格相减的差值。

如果差值为正则意味股票在上涨，如果差值为负则意味股票在下跌，我们可以将每日股票的收益转化为差分数组，求出此数组中连续子序列和的最大值，即为最大收益。

详解

根据上述分析，我们用 profits[i] 表示第 i 天进行一笔交易能获得的最大收益，那么第 i 天会产生两种决策：

1. 第 i 天当天买入，此时收益为 0
2. 第 i 天之前买入，第 i 天卖出，此时可获得最大收益为第 i -1 天的最大收益 profits[i - 1] 加上今天股票价格 prices[i] 与昨天价格 prices[i - 1] 的差值

那么第 i 天可以获得的最大收益为这两种情况的最大值，即：profits[i] = max(0, profits[i - 1] + (prices[i] - prices[i - 1]))，

我们只需根据以上公式递推，即可得到每日可获取最大收益数组 profits[]。

我们通过一个变量 maxProfit 来保存已获取的最大收益，然后在计算每日最大收益的过程中与 maxProfit 做比较，最终计算出最大收益。

代码

function maxProfit(prices) {
  let minPrice = 0;
  let maxProfit = 0;

  prices.forEach((price, index) => {
    if (index === 0) { // 初始化最小价格为第一个元素
      minPrice = price;
    } else if (price < minPrice) { // 遍历过程中发现最小价格，则重新赋值
      minPrice = price;
    } else if (price - minPrice > maxProfit) { // 比较当日卖出收益与当前已获取的最大收益
      maxProfit = price - minPrice;
    }
  });

  return maxProfit;
};

复杂度分析

• 时间复杂度：O(n) O(n)
• 空间复杂度：O(n)O(n)

打家劫舍、零钱兑换和跳跃游戏

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

方法一 用迭代的方式遍历计算

思路

由于不可以在相邻的房屋闯入，所以在当前位置 n 房屋可盗窃的最大值，要么就是 n-1 房屋可盗窃的最大值，要么就是 n-2 房屋可盗窃的最大值加上当前房屋的值，二者之间取最大值 动态规划方程：dp[n] = MAX( dp[n-1], dp[n-2] + num )

详解

1. 获取房间的个数，如果为 0，就直接返回 0，
2. 如果为 1，就直接返回数组第一个值，
3. 设置三个变量 sumTemp 临时求和值，sumBefore n-2 总和，sumAfter n-1 总和
4. 初始化 3 个变量的值，
5. 循环 len-2 次求动态规划的值 nums[i] 为当前房间值

const rob = function (nums) {
  const len = nums.length;
  if (len === 0) return 0;
  if (len === 1) {
    return nums[0];
  }
  if (len === 2) {
    return Math.max(nums[0], nums[1]);
  }

  let sumTemp = 0;
  let sumBefore = nums[0];
  let sumAfter = Math.max(nums[0], nums[1]);
  let i = 2;
  while (i < len) {
    sumTemp = Math.max(sumAfter, sumBefore + nums[i]);
    sumBefore = sumAfter;
    sumAfter = sumTemp;
    i++;
  }
  return sumAfter;
};

复杂度分析：

• 时间复杂度：O(n)O(n)

  只需要单循环 nn 长度的数组 O(n-2)O(n−2)，故时间复杂度为 O(n)O(n)

• 空间复杂度：O(1)O(1)

方法二

思路

由于不可以在相邻的房屋闯入，所以在当前位置 n 房屋可盗窃的最大值，要么就是 n-1 房屋可盗窃的最大值，要么就是 n-2 房屋可盗窃的最大值加上当前房屋的值，二者之间取最大值 动态规划方程：dp[n] = MAX( dp[n-1], dp[n-2] + num ) 总体的思路是一样的，方法一中，数组长度为 0，1，2 中单独处理，切换设计的求和变量过多，6 个可以利用数组变量优化。

详解

1. 获取房间的个数，如果为 0，就直接返回
2. 设置一个 len+1 的数组变量，初始化数组中的第一个和第二个对象，这边就可以不用单独处理数组长度为 1 和 2 的情况
3. 每次的循环求和的结果都记录在对于长度的数组对象中，不必声明多个变量暂存。
4. 然后利用动态规划公式查找 n 个最大的数组和的值

const rob = function (nums) {
  const len = nums.length;
  if (len === 0) return 0;
  const dp = new Array(len + 1);
  dp[0] = 0;
  dp[1] = nums[0];
  for (let i = 2; i <= len; i++) {
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
  }
  return dp[len];
};

复杂度分析

• 时间复杂度：O(n)O(n)

  只需要单循环 nn 长度的数组 O(n-2)O(n−2)，故时间复杂度为 O(n)O(n)

• 空间复杂度：O(1)O(1)