Dynamic Programming - Memoization 动态规划 - 记忆法

Introduction

在学习掘金前端算法与数据结构面试这本小册的时候，啃到动态规划部分有点啃不动。在youtube找了一个很好的视频专门讲动态规划，这个系列将会记录我学习动态规划的笔记与心得。视频把动态规划解法分为了memoization和tabulation两种形式，这篇文章主要讲memoization。

斐波那契数列
gridTraveler
Memoization Recipe
canSum
howSum
bestSum
- 递归解法
- Memoization解法

斐波那契数列

要打开动态规划（Dynamic Programming）的大门，我们首先来看一下斐波那契数列，根据维基百科上的定义，斐波那契数列由0和1开始，之后的斐波那契数由之前的两数相加得出，由此可知斐波那契数列是：

1、1、2、3、5、8、13、21、24、55、89、144、233...

在数学上，斐波那契数以递归的方法来定义：

F(0)=0
F(1)=1
F(n) =F(n-1)+F(n-1)

leetcode第509题就以此为题干：

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,
F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.
Given n, calculate F(n).

递归解法

我们试着用递归的方式来解这道题：

const fib = (n) => {
  if (n <= 2) return 1
  return fib(n - 1) + fib(n - 2)
}

打印fib(5), fib(6), fib(7), 都没问题，分别输出5、8、13，但是一旦打印较大的数字例如fib(50)就会变得很慢，在性能上有大问题。提前告诉大家，它的时间复杂度是O(2^n)。

复杂度分析

在解释为什么上面那种解法时间复杂度大之前，我们先来看几组例子分析一下时间空间复杂度，算是热热身，真正搞懂递归的时间空间复杂度怎么算。

例1

const foo = (n) => {
  if (n <= 1) return
  foo(n - 1)
}

对于foo(5)来说，函数跑了5次。那么对于f(n)来说就会跑n次。所以时间复杂度是O(n)。

那么空间复杂度呢？对于每次调用，函数执行上下文都会被推入调用栈，所以空间复杂度也是O(n)。

例2

const foo = (n) => {
  if (n <= 1) return
  foo(n - 1)
}

对于foo(6)跑了4次，对于foo(7)会跑5次，对于foo(8)会跑5次，对于foo(9) 会跑6次......总结一下规律就是Math.ceil(n/2) + 1, 时间复杂度是大约是O (n/2)，根据Big O Notation，我们在计算时间复杂度的时候，可以把常数项忽略，所以这个函数的时间复杂度大约也是O(n)。此时时间复杂度也是O(n)。

例3

const dib = (n) => {
  if (n <= 1) return
  dib(n - 1)
  dib(n - 1)
}

画图：

可以看到树的高度是n，对于第一层来说2^0个节点，对于第二层有2^1个节点，第三层2^2，第n层2^n，一个节点意味着函数被调用一次。所以在这个算法中，时间复杂度为O(2^n)。

但这次空间复杂度不是O(2^n)，我们主要看调用栈里的函数最多的时候有多少个，它和输入n的关系是什么。

当我们递归第一行dib(n-1)的时候，它会一直行进到dib(1-1)，也就是叶子节点那里。此时调用栈中大约有n个函数，再继续就要把dib(0)出栈，然后走下一行的dib(n-1)，如上图所画的绿色路线。所以这个算法的空间复杂度最大是O(n)。

例4

const lib = (n) => {
  if (n <= 1) return
  lib(n - 2)
  lib(n - 2)
}

对于这个例子，它和上面唯一的区别就是，n-1变成了n-2。

相应的，时间复杂度是O(2^(n/2))，空间复杂度是O(n/2)，简化一下和上个例子的时间空间复杂度还是一样的。

最后看回我们斐波那契数列算法：

const fib = (n) => {
  if (n <= 2) return 1
  return fib(n - 1) + fib(n - 2)
}

它的时间复杂度应该介于dib和lib之间，而dib和lib都是2^n，可以推想fib的时间复杂度也是2^n。

对于fib(7)，函数调用最满的时候，时间复杂度也是2^n。空间复杂度大约是O(n)，调用栈里最多有n个函数。

在计算fib(50)的时候，函数跑了很多次，如下：

当我们以fib(7)为例画出递归树图之后会发现，很多节点的值被重复计算了，浪费了大量计算资源。

Memoization解法

如果我们能记住已经计算过的结果，就能大大提高算法速度。我们往fib函数加上第二个参数memo，如下：

const fib = (n, memo = {}) => {
  if (n in memo) return memo[n]
  if (n <= 2) return 1
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
  return memo[n]
}

如果在memo里能找到这个n，就返回memo[n]，如果找不到，就把这次返回的结果记录到memo[n]里。这样我们就避免了重复计算。

我们来计算一下这个解法的时间和空间复杂度，以fib(6)为例：

再看fib(7)``fib(8)``fib(9)，我们会发现函数被调用的次数实际上就是2n，被推入栈的函数数量也是2n，所以这个解法的时间和空间复杂度都是O(n)。

gridTraveler

问题描述

gridTraveler是一个经典的动态规划问题，题目是这样的：

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time. Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner. The test cases are generated so that the answer will be less than or equal to 2 * 109.

我们可以想象有一个绿色的小人站在左上角，他唯一能做的选择是往下或者往右走，直到走到右下角。我们可以用递归的方式来解这道题：

如果他如上图向下走了一步，这个问题就可以变成是3*2格子的问题，如果他向右走了一步，这个问题就可以变成是2*3格子的问题。他可以走到右下角的所有方式等于向下走的方式加上向右走的方式。

随着他一直走，最终会走到边缘情况例如1*1的格子，这个时候就只有一种走法。如果是0*1或者1*0的格子，就是没有走法。

递归解法

根据以上的描述，我们可以写一个最简单的写法：

function gridTraveler(m, n) {
  if (m == 1 && n == 1) return 1
  if (m == 0 || n == 0) return 0
  return gridTraveler(m - 1, n) + gridTraveler(m, n - 1)
}

这种解法确实能够解决问题，但是对于较大的网格，计算就会很慢，我们可以看看下面这张树状图：

图中gridTraveler(1,2)、gridTraveler(2,1)、gridTraveler(1,1)等都被重复计算了，我们可以用memoization来优化这个问题。

Memoization解法

function gridTraveler(m, n, memo = {}) {
  const key = m + ',' + n
  if (key in memo) return memo[key]
  if (m == 1 && n == 1) return 1
  if (m == 0 || n == 0) return 0
  memo[key] = gridTraveler(m - 1, n, memo) + gridTraveler(m, n - 1, memo)
  return memo[key]
}

往gridTraveler 里加上第三个参数 memo，这样我们就能记住已经计算过的结果，避免重复计算。key使用m + ',' + n来表示，这样就能唯一标识一个路线。

复杂度分析

对于时间复杂度来说，取决于需要计算的字问题数量，在这个问题中，我们需要计算m*n个字问题，每个子问题只需要计算一次就会被记入缓存，无需再次计算。所以时间复杂度是O(m*n)。对于空间复杂度来说，对于一个 m x n 的网格，我们最多需要存储 m x n 个子问题的结果，因为每个位置都对应着一个子问题。因此，memo 对象的空间复杂度与需要计算的子问题数量成正比。空间复杂度为O(m*n)。

Memoization Recipe

从上面两个例子，我们可以总结出使用memoization解决动态规划问题的两个步骤：

Make it work

visualise the problem as a treeVisual
implement the treeVisual using recursion
- think about leaf as edge cases
test it

Make it efficient

add memo object
add base case to return memo values
store return values into memo

canSum

问题描述

Write a function canSum(targetSum, numbers) that takes in a targetSum and an array of numbers as arguments. The function should return a boolean indicating whether or not it is possible to generate the targetSum using numbers from the array.

You may use an element of the array as many times as needed. You may assume that all input numbers are nonnegative.

canSum(7, [5,3,4,7]) -> true canSum(6, [5,3]) -> false

思路分析

以简单的例子canSum(7, [5,3,4,7])为例，我们可以用递归的方式来解决这个问题。我们可以把这个问题想象成一个树状图，每个节点都是一个targetSum，每个节点的子节点是targetSum - num，num是数组里的一个元素。根节点是最开始的targetSum，如果有一个节点的值是0，就返回true，如果最后的叶子结点会是负数，就返回false。

如下图：

递归解法

const canSum = (targetSum, numbers) => {
  if (targetSum == 0) return true
  if (targetSum < 0) return false

  for (let num of numbers) {
    const remainder = targetSum - num
    // 只要这个for loop里有一个true，就返回true，false的话继续循环
    if (canSum(remainder, numbers) == true) {
      return true
    }
  }
  // 直到for loop结束，都没有返回true，就返回false
  return false
}

如果我们尝试console.log(canSum(300, [7,14]))会发现这个函数运行的很慢，来分析一下它的复杂度。

首先是空间复杂度，可以通过树的高度，也就是递归调用栈的深度来计算。对于canSum(7, [5,3,4,7])来说，树的高度最多是7，所以空间复杂度是O(m)。然后是时间复杂度，观察影响分叉的因素，从每上一层到下一层，节点的数量如何变化。每一层的节点数量大约是上一层*n的关系，而树的高度又是m，所以时间复杂度是O(n^m)。

Memoization解法

还是用memo来记忆，代码如下：

- const canSum = (targetSum, numbers) => {
+ const canSum = (targetSum, numbers, memo={}) => {
+ if(targetSum in memo) return memo[targetSum]
  if(targetSum == 0) return true
  if(targetSum < 0) return false

  for (let num of numbers) {
    const remainder = targetSum - num
-     if(canSum(remainder, numbers) == true) {
+     if(canSum(remainder, numbers, memo) == true) {
+     memo[targetSum] = true
      return true
    }
  }
+ memo[targetSum] = false
  return false
}

分析时间复杂度，我们把targetSum当作m，numbers的长度当作n，在最坏的情况下，每个targetSum都需要计算一次，而对于每个targetSum，我们都需要遍历一遍numbers，所以时间复杂度是O(n*m)。

分析空间复杂度，调用栈中最多会推入m个函数，或者说memo对象的空间复杂度与targetSum成正比，所以空间复杂度是O(m)。

howSum

问题描述

Write a function howSum(targetSum, numbers) that takes in a targetSum and an array of numbers as arguments. The function should return an array containing any combination of elements that add up to exactly the targetSum. If there is no combination that adds up to the targetSum, then return null.

给定一个目标和targetSum和一个数组numbers，返回一个数组，数组里的元素相加等于targetSum。如果没有这样的组合，返回null。

howSum和canSum很类似，区别仅仅在于返回值不是布尔值，而是满足条件的数组，且只需要返回一个就行。

递归解法

function howSum(targetSum, numbers) {
  // 如果targetSum被一直减到0，就返回空数组，准备好接收结果
  if (targetSum == 0) return []
  // 如果targetSum被一直减到小于0，就返回null
  if (targetSum < 0) return null

  for (let num of numbers) {
    const remainder = targetSum - num
    const res = howSum(remainder, numbers)
    if (res !== null) {
      return [...res, num]
    }
  }

  // 如果for loop结束，都没有返回任何满足条件的数组，就返回null
  return null
}

但它依然有重复计算的问题。如果targetSum为m，数组numbers的长度为n。就时间复杂度而言，在递归树中，每个节点都有n个子节点可以选择，且该函数探索了元素的所有可能组合，递归树的高度可以达到m，所以时间复杂度是O(n^m)。就空间复杂度而言，树的深度是m，调用栈最多有m个函数，空间复杂度为m。

Memoization解法

function howSum(targetSum, numbers, memo = {}) {
  if (targetSum in memo) return memo[targetSum]
  if (targetSum == 0) return []
  if (targetSum < 0) return null

  for (let num of numbers) {
    const remainder = targetSum - num
    const res = howSum(remainder, numbers, memo)
    if (res !== null) {
      memo[targetSum] = [...res, num]
      return memo[targetSum]
    }
  }

  memo[targetSum] = null
  return null
}

为什么这个解法的时间复杂度是O(n*m)，而不是O(n^m)呢？因为我们在memo里存储了每个targetSum的结果，所以不需要重复计算。每个targetSum最多只会被计算一次，每次会遍历numbers数组，所以时间复杂度是O(n*m)。

bestSum

Write a function bestSum(targetSum, numbers) that takes in a targetSum and an array of numbers as arguments.

The function should return an array containing the shortest combination of numbers that add up to exactly the targetSum.

If there is a tie for the shortest combination, you may return any one of the shortest.

递归解法

和之前的howSum代码很类似，只是在返回的时候，我们要比较当前的组合和之前的组合，如果当前组合比之前的组合短，或者之前的组合是null，就更新最短组合。

function bestSum(targetSum, numbers) {
  if (targetSum == 0) return []
  if (targetSum < 0) return null

  let shortestCombination = null

  for (let num of numbers) {
    const remainder = targetSum - num
    const res = bestSum(remainder, numbers)
    if (res !== null) {
      const combination = [...res, num]
      if (shortestCombination === null || combination.length < shortestCombination.length) {
        shortestCombination = combination
      }
    }
  }

  return shortestCombination
}

这个解法的时间复杂度是O(n^m * m)，空间复杂度是O(m^2)。对于时间复杂度，n^m是因为递归树的高度是m，每个节点有n个子节点，m是因为我们要存储每个targetSum的结果。存储这个结果的空间复杂度是O(m)。如果没有这样的组合，返回null。对于空间复杂度，m^2是因为我们要存储每个targetSum的结果，每个targetSum的结果是一个长度为m的数组。

Memoization解法

- function bestSum(targetSum, numbers) {
+ function bestSum(targetSum, numbers, memo={}) {
  if(targetSum in memo) return memo[targetSum]
  if(targetSum == 0) return []
  if(targetSum < 0 ) return null


  let shortestCombination = null

  for (let num of numbers) {
    const remainder = targetSum - num
- const res = bestSum(remainder, numbers)
+ const res = bestSum(remainder, numbers, memo)


    if(res !== null) {
      const combination = [...res, num]
      if(shortestCombination === null || combination.length < shortestCombination.length) {
        shortestCombination = combination
      }
    }
  }
+ memo[targetSum] = shortestCombination
  return shortestCombination
}

对于时间复杂度而言，每个targetSum最多只会被计算一次，每次会遍历numbers数组，所以时间复杂度是O(n*m*m)。 n*m是因为递归树的高度是m，每个节点有n个子节点，m是因为我们要做[...res, num]这个操作，这个操作的时间复杂度是O(m)，因为res的长度最多是m。

对于计算空间复杂度而言，对于每个targetSum，我们都要存储一个数组，数组的长度最多是m，所以空间复杂度是O(m^2)。