洛清寒前端进阶

# 动态规划

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，n<=39）。

# 1、暴力递归fib

function fib(n){
    if(n==1 || n==2) return 1
    return  fib(n-1) + fib(n-2)
}

console.time('fib')
console.log(fib(100))
console.timeEnd('fib')
1
2
3
4
5
6
7
8

会发现根本计算不出来，递归调⽤很复杂，从Fibonacci(n-1)+Fibonacci(n-2)明显看出使用的是递归，此题用递归两三行代码即可搞定。但是，若出题者准备着一个超大的n，那么很有可能会 Stack Overflow（递归的本质就是栈），为什么会栈溢出？因为重复计算，举个栗子：

当n=4时，

Fibonacci(4) = Fibonacci(3) + Fibonacci(2)
​ = Fibonacci(2) + Fibonacci(1) + Fibonacci(1) + Fibonacci(0)
​ = Fibonacci(1) + Fibonacci(0) + Fibonacci(1) + Fibonacci(1) + Fibonacci(0);
1
2
3

由于我们的代码并没有记录Fibonacci(1)和Fibonacci(0)的结果，对于程序来说它每次递归都是未知的，因此光是n=4时Fibonacci(1)就重复计算了3次之多。

递归算法的时间复杂度怎么计算？⼦问题个数乘以解决⼀个⼦问题需要的时间。⼦问题个数，即递归树中节点的总数。显然⼆叉树节点总数为指数级别，所以⼦问题个数为 O(2^n)。

解决⼀个⼦问题的时间，在本算法中，没有循环，只有 f(n - 1) + f(n - 2) ⼀个加法操作，时间为 O(1)。所以，这个算法的时间复杂度为 O(2^n)，指数级别，爆炸。

# 2、中间存储fib (自顶向下,递归)

明确了问题，其实就已经把问题解决了⼀半。即然耗时的原因是重复计算，那么我们可以造⼀个「备忘录」，每次算出某个⼦问题的答案后别急着返回，先记到「备忘录」⾥再返回；每次遇到⼀个⼦问题先去「备忘录」⾥查⼀查，如果发现之前已经解决过这个问题了，直接把答案拿出来⽤，不要再耗时去计算了。 ⼀般使⽤⼀个数组充当这个「备忘录」，当然你也可以使⽤哈希表（字典），思想都是⼀样的。

// 中间存储fib
function fib1(n) {
    let memo = {};
    return helper(memo, n)
}

function helper(memo, n) {
    if (n == 1 || n == 2) {
        // 前两个
        return 1
    }
    // 如果有缓存，直接返回
    if (memo[n]) return memo[n];
    // 没缓存
    memo[n] = helper(memo, n - 1) + helper(memo, n - 2)
    return memo[n]
}

console.time('fib')
console.log(fib1(1000))
console.timeEnd('fib')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

递归算法的时间复杂度怎么算？⼦问题个数乘以解决⼀个⼦问题需要的时间。

⼦问题个数，即图中节点的总数，由于本算法不存在冗余计算，⼦问题就是 f(1), f(2), f(3) ... f(20)，数量和输⼊规模 n = 20 成正⽐，所以⼦问题个数为 O(n)。

解决⼀个⼦问题的时间，同上，没有什么循环，时间为 O(1)。 所以，本算法的时间复杂度是 O(n)。⽐起暴⼒算法，是降维打击。

⾄此，带备忘录的递归解法的效率已经和动态规划⼀样了。实际上，这种解法和动态规划的思想已经差不多了，只不过这种⽅法叫做⾃顶向下，动态规划叫做⾃底向上。

啥叫⾃顶向下？注意我们刚才画的递归树（或者说图），是从上向下延伸，都是从⼀个规模较⼤的原问题⽐如说 f(20)，向下逐渐分解规模，直到 f(1) 和 f(2) 触底，然后逐层返回答案，这就叫「⾃顶向下」。

啥叫⾃底向上？反过来，我们直接从最底下，最简单，问题规模最⼩的 f(1) 和 f(2) 开始往上推，直到推到我们想要的答案f(20)，这就是动态规划的思路，这也是为什么动态规划⼀般都脱离了递归，⽽是由循环迭代完成计算。

# 3、动态规划fib（自底向上,迭代）

我们可以把这个备忘录独⽴出来成为⼀张表，就叫做 DP table吧，在这张表上完成「⾃底向上」的推算岂不美哉！

// 动态规划fib
function fib2(n) {
    let dp = []
    dp[1] = dp[2] = 1
    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}
console.log(fib2(1000))
1
2
3
4
5
6
7
8
9
10

# 4、零钱找零问题

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
1
2
3

示例 2:

输入: coins = [2], amount = 3
输出: -1
1
2

说明:你可以认为每种硬币的数量是无限的。

# 分析

如果我们有面值为1元、3元和5元的硬币若干枚，如何用最少的硬币凑够11元？ (表面上这道题可以用贪心算法，但贪心算法无法保证可以求出解，比如1元换成2元的时候)，我们用d(i)=j来表示凑够i元最少需要j个硬币。于是我们已经得到了d(0)=0，表示凑够0元最小需要0个硬币。

当i=1时，只有面值为1元的硬币可用，因此我们拿起一个面值为1的硬币，接下来只需要凑够0元即可，而这个是已经知道答案的，即d(0)=0。所以，d(1)=d(1-1)+1=d(0)+1=0+1=1。

当i=2时，仍然只有面值为1的硬币可用，于是我拿起一个面值为1的硬币，接下来我只需要再凑够2-1=1元即可(记得要用最小的硬币数量)，所以，d(2)=d(2-1)+1=d(1)+1=1+1=2。

当i=3时，我们能用的硬币就有两种了：1元的和3元的。 既然能用的硬币有两种，我就有两种方案。

  • 如果我拿了一个1元的硬币，我的目标就变为了： 凑够3-1=2元需要的最少硬币数量。即d(3)=d(3-1)+1=d(2)+1=2+1=3。这个方案说的是，我拿3个1元的硬币。
  • 第二种方案是我拿起一个3元的硬币，我的目标就变成：凑够3-3=0元需要的最少硬币数量。即d(3)=d(3-3)+1=d(0)+1=0+1=1。 这个方案说的是，我拿1个3元的硬币。

好了，这两种方案哪种更优呢？ 记得我们可是要用最少的硬币数量来凑够3元的。所以，选择d(3)=1，怎么来的呢？具体是这样得到的：d(3)=min{d(3-1)+1, d(3-3)+1}。

从以上的文字中， 我们要抽出动态规划里非常重要的两个概念：状态和状态转移方程。

上文中d(i)表示凑够i元需要的最少硬币数量，我们将它定义为该问题的"状态"，最终我们要求解的问题，可以用这个状态来表示：d(11)，即凑够11元最少需要多少个硬币。 那状态转移方程是什么呢？既然我们用d(i)表示状态，那么状态转移方程自然包含d(i)， 上文中包含状态d(i)的方程是：d(3)=min{d(3-1)+1, d(3-3)+1}。没错， 它就是状态转移方程，描述状态之间是如何转移的。当然，我们要对它抽象一下，

d(i)=min{ d(i-vj)+1 }，其中i-vj >=0，vj表示第j个硬币的面值;
1

有了状态和状态转移方程，这个问题基本上也就解决了。

# 实现

var amount = 12,
    coins = [1, 2, 3, 5, 6, 10];

function coinChange(amount, coins) {
	// dp[i]表示总金额为i时所需硬币的最小数量
	// 我们希望dp[11]表示兑换11块钱时所需硬币的最小数量，下标为11的时候，总长度就是12
	var dp = Array(amount + 1).fill(Infinity)
	dp[0] = 0

	// 遍历各种coin
	coins.map(coin => {
		// 先取当前coin, j = coin ...11
		for (var j = coin; j < dp.length; j++) {
			dp[j] = Math.min(dp[j - coin] + 1, dp[j])
			// 比如j=10，coin=5，当我拿起这个5元的时候，剩下还需要凑够5元，
			// 那么dp[10]=dp[10-5]+1，即dp[10]=dp[5]+1, 
			// 也是可以直接取dp[j]，但是有可能不是最小的，所以就取两种的较小者，用min。
		}
	})
	return dp[amount] == Infinity ? -1 : dp[amount]
}

console.log(coinChange(amount,coins))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 5、贪心算法

贪心算法是⼀种求近似解的思想。当能满⾜大部分最优解时就认为符合逻辑要求。还⽤零钱找零这个案例为例，考虑使⽤贪心算法解题: 比如当找零数为 36 时，从硬币数的最⼤值 20 开始填充,填充不下后再用10来填充，以此类推，找到最优解。

// 贪心
class Change {
  constructor(changeType) {
    this.changeType = changeType.sort((r1, r2) => r2 - r1)
  }
  makeChange(amount) {
    const arr = []
    for (let i = 0; i < this.changeType.length; i++) {
      while (amount - this.changeType[i] >= 0) {
        arr.push(this.changeType[i])
        amount = amount - this.changeType[i]
      }
    }
    return arr
  }
}

const change = new Change([1, 5, 10, 20, 50, 100])
console.log(change.makeChange(36))
console.log(change.makeChange(136))
console.log('-'.repeat(100))
const change1 = new Change([1, 3, 4])
console.log(change1.makeChange(6)) // 其实33最好
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

贪心算法相对简单，就是先怼最⼤的，⼤部分情况都OK，但是有些情况不是最优解。

console.log('-'.repeat(100))
const change1 = new Change([1, 3, 4])
console.log(change1.makeChange(6)) // 打印出来是4,1,1,  其实是3，3最好
1
2
3
Last Updated: 3/29/2020, 2:48:05 PM

←