DP在实际开发中的应用
#动态规划 #技术 #算法

1 前言

在做需求时，遇到过这么一个场景：

用户设定一张试卷的总分，我们随机从题库中选择几道不同的题目，使它们的分值刚好能组成这张试卷。

这需求算法味儿挺浓的，感觉挺有意思的，于是就写了个demo实现了一下。

See the Pen 一键组卷-core by Misakisaysyes (@misakisaysyes) on CodePen.

2 需求分析

我们给这个需求套一组数据，就可以把它变成一道类似于leetcode的题目

用户需要一张100分的试卷。
现在题库中有一组人民币面值分数的题目：[1分, 5分, 10分, 20分, 50分], 这些题目的数量分别为：[5道, 2道, 4道, 2道, 4道]。
请随机从题库中挑出几道内容不同的题目，组成总分为100的试卷。

对于这道leetcode，我们先思考🤔两个问题：

问题一 

在当前的条件下：有5道1分、2道5分、4道10分、2道20分、4道50分的题目。

请问在满足题目数量限制的条件下，有多少种选法，能使得所选题目的分数总和为100？

问题二

解决了第一个问题后，我们得到n个满足条件的组合。

随机选一个，假设选了 50 + 50 = 100。

即现有的4道50分的题，我们需要从中选择不重复的2道，凑成试卷，这又该怎么选？

问题一本质是个多重背包问题，可以用动态规划的方式解决。

问题二本质是个求组合的问题，从C(4, 2)个组合中选一个☝作为结果，这个问题求解方式很多（可以暴力求解），其中也可以用到动态规划。

3 关于动态规划

动态规划 即 Dynamic Programming（DP）。

它是针对一类问题的优化后的解决方案，这类问题能被划分为多个重叠子问题。

3.1 重叠子问题

那什么是重叠子问题？

举个最常见的例子🌰：斐波那契数列

第1位 第2位 第3位 第4位 第5位
1 1 2 3 5

我们知道斐波那契的递推公式是：第 n 位 = 第 n - 1 位 + 第 n - 2 位

也就是

当我们求第4位时，等价在问：第2位等于多少？第3位等于多少？

当我们求第5位时，等价在问：第3位等于多少？第4位等于多少？

第3位等于多少这个问题，在求第4位和第5位时都被问了一遍，故它是个重叠子问题。

所以，重叠子问题就是由大问题拆解而来，并在求解过程中会被重复问到的小问题。

而动态规划就是一种解决能被划分为重叠子问题这类问题的求解方法。

3.2 从递归到动态规划

但其实我们可以从很多地方了解到，解决这类问题的方法是递归。

但递归有个缺陷，就是会重复求解重叠子问题，而导致一些浪费。

比如在斐波那契这个例子中：

若用递归，那我们在求第5位等于多少时，就必须再求一遍第3位等于多少。

尽管第3位等于多少这个问题在求第4位等于多少时算过一遍。

而动态规划算法就正好解决了这种浪费。它最朴素的核心思想就是：

在内存中开一个缓存数组，每求解一个重叠子问题，就将答案记录下来。

当再次问到该子问题时，就可以直接从缓存中取答案，从而减少计算次数。

所以，动态规划可以理解为进化后的递归。

这里就用上文中的问题二稍加变化，来演绎一下递归是如何进化成动态规划的。

变形后的问题二：

从4道不同的题目中随机选2道，请问能得到多少种组合？

即 求C(4, 2)等于多少？

tips: 在基于枚举思想的算法里，能求出所有情况数（组合数），就必然能求出所有情况（列举出所有组合）。

3.3 原始递归求C(4, 2)

3.3.1 分析递推关系

已知数组[a, b, c, d]，随机选2元素，类似于[a, b]、[b, c]、[c, d]…这种两元素组合共有多少？

借助组合数学中集合这个工具，有如下分析：

设全集U为：[a, b]、[b, c]、[c, d]… 即[a, b, c, d]中所有2元素组合。

设子集A为：[a, b]、[a, c]… 即所有含a的2元素组合。

设子集B为：[b, c]、[c, d]… 即所有不含a的2元素组合。

由我们赋予U、A、B的含义，可以得到如下关系：

U = A ∪ B

A ∩ B = ∅

再借助容斥原理，可得：

|U| = |A ∪ B| = |A| + |B| - |A ∩ B|

因为 A ∩ B = ∅ => |A ∩ B| = 0

所以 |U| = |A| + |B|

其中

|U| = C(4, 2)

|A| = C(3, 1) // 在数组[b, c, d]中随机再选1个元素的组合数

|B| = C(3, 2) // 在数组[b, c, d]中随机再选2个元素的组合数

所以得到：

C(4, 2) = C(3, 1) + C(3, 2)

用同样的方法分析C(3, 2)可得：

C(3, 2) = C(2, 1) + C(2, 2)

…

所以通过类比推理，最后得到递推关系式：

C(m, n) = C(m - 1, n - 1) + C(m - 1, n)

3.3.2 递归代码

得到递推关系式后再思考一下边界条件，便可得到如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const testArr = [a, b, c, d]
const Cmn = (arr, num) => {

    // C(m, n) m = 0 不合法 返回0
    if (!arr.length) { return 0 }

    // C(m, n) m < n 不合法 返回0
    if (arr.length < num) { return 0 } 

    // C(m, 0) = 1
    if (!num) { return 1 }

    // C(x, x) = 1  
    if (arr.length === num) { return 1 }
    
    return Cmn(arr.slice(1), num - 1) + Cmn(arr.slice(1), num)
}
console.log('C(4, 2) = ', Cmn(testArr, 2))

原始递归在求解这个问题时，我们可以自顶向下地画出一颗树来：

1.png

从图示可看出，C(2, 1)等于多少？这问题，前后被问了两次，也被回答了两次。

那是不是可以优化一下？

3.4 记忆化递归求C(4, 2)

最朴素的优化方法，就是记忆化递归。

基本操作就是弄个缓存，把所有求解过的子问题的答案都存下。

当再次问到该问题时，就直接从缓存中拿答案，而不用再去求解了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const testArr = [a, b, c, d]

const memo = {}
const Cmn = (arr, num) => {

    if (!arr.length) { return 0 }
    if (arr.length < num) { return 0 } 

    const key = `${arr.length}-${num}`
    if(memo[key]) { return memo[key] }
    if (!num) { memo[key] = 1 }
    if (arr.length === num) { memo[key] = 1 }
    memo[key] = Cmn(arr.slice(1), num - 1) + Cmn(arr.slice(1), num)

    return memo[key]
}
console.log('C(4, 2) = ', Cmn(testArr, 2))

乍一看上去这种优化思路和动态规划一样，都是开个缓存把结果都存起来。

但递归下的缓存大小是没法优化的，它必定存储了递归过程中每个节点的值。

比如

用带缓存的递归求C(4, 2)，虽然不用重复求C(2, 1)了，但缓存中一定会存下C(4, 2)、C(3, 2)、C(3, 1)、C(2, 2)、C(2, 1)、C(2, 0)、C(1, 1)、C(1, 0)这8个节点的值。

而事实上，只有C(2, 1)被重复求解了。也就是缓存值其实只有C(2, 1)是有意义的，其它都没用，浪费空间了。

这是因为递归的这种自顶向下，倒推的求解形式所导致的。

那有没有办法，去优化一下缓存空间呢？以最小的代价，来解决这类重叠子问题。

3.5 动态规划求C(4, 2)

答案是有的，那就是动态规划。

动态规划采取了自底向上的解法。也就是不同于递归从C(4, 2)开始求解，会从C(0, 0)、C(1, 0)…开始计算，直到算到C(4, 2)。

自底向上求解的好处在于：

可以通过递推关系，预测出当前子问题的结果是否会用到将来的求解中。

如果被用到了，就缓存下来，如果不会再被用到了，那就把它的空间给释放掉。

这样就达到了优化缓存大小的目的。

还是C(4, 2)这个例子，用动态规划的方式改写一遍记忆化递归的解法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const testArr = [a, b, c, d]
const Cmn = (arr, num) => {
    let dp = new Array(arr.length + 1).fill()
    dp = dp.map(_ => {
        let arr = new Array(num + 1).fill(0)
        arr[0] = 1
        return arr
    })

    for (let i = 1; i <= arr.length; i++) {
        for (let j = 1; j <= num && j <= i; j++) {
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
        }
    }
    return dp[arr.length][num]
}
console.log('C(4, 2) = ', Cmn(testArr, 2))

我们开了一个二维数组dp当缓存，也是放8个节点。

然后根据递推关系式C(m, n) = C(m - 1, n - 1) + C(m - 1, n)写出状态转移方程dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]。

这样写的话，本质和前面的记忆化递归没啥两样。

但是细看状态转移方程会发现：

对于dp表而言，第i行第值，只与第i - 1行的值相关，和第i - 2行的值无关。

比如在C(4, 2)中，第3行的值只与第4行相关，第4行第值又只与第3行第值相关。

4.png

所以，在这里，完全可以只缓存一行（3个节点的结果），而不用开二维数组缓存所有子问题的结果。

但如果只缓存一行，就会有这样的情况：

当计算第3行时，使用缓存里第2行的结果。当计算第4行时，需要用第3行的结果。

所以这时，需要考虑更新缓存。

这里再回到状态转移方程分析，可以发现，当前所求值，其依赖的值都不会在所求值的右上方。

比如C(4, 1)的结果只与C(3, 0)和C(3, 1)有关，与右上方的C(3, 2)无关。

5.png

也就是说，从右向左地更新缓存，便可在更新缓存的同时，不影响值的计算。

2.png

这样分析下来，dp的解法就可以优化为：

1
2
3
4
5
6
7
8
9
10
11
12
const testArr = [a, b, c, d]
const Cmn = (arr, num) => {
    let dp = new Array(num + 1).fill(0)
    dp[0] = 1
    for (let i = 1; i <= arr.length; i++) {
        for(j = i; j > 0; j --) {
            dp[j] = dp[j - 1] + dp[j]
        }
    }
    return dp[num]
}
console.log('C(4, 2) = ', Cmn(testArr, 2))

在解决C(4, 2)这个问题上，这种优化后的dp只用缓存3个节点，相比于记忆化递归的方式节约了至少一半的空间。

4 回到需求

以上就是我关于动态规划的一点理解。

现在回到需求本身。

这个需求有两个问题要思考，详见2 需求分析

问题二求C(4, 2)组合上文已经论述过了，这里就主要看看问题一：

用户需要一张100分的试卷，现在我们题库中有一组人民币面值分数的题目：[1分, 5分, 10分, 20分, 50分]，这些题目的数量分别为：[5道, 2道, 4道, 2道, 4道]，请求出所有的组合数

这是一个很典型的多重背包问题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const combinations = (total, nums, amount) => {
    let dp = new Array(total + 1).fill(0)
    dp[0] = 1

    for(let i = 0; i < nums.length; i++) {
        for (let j = total; j >= nums[i]; j--) {
            for(let k = 1; k <= amount[i] && j >= k*nums[i]; k++) {
                dp[j] += dp[j - k*nums[i]]
            }
        }
    }

    return dp[total]
}
console.log(combinations(100, [1, 5, 10, 20, 50], [5, 2, 4, 2, 4]))

背包问题是动态规划中一类问题，其结构如下：

6.png

背包问题可以分为0-1背包和完全背包，多重背包是0-1背包的变种。

4.1 0-1背包和完全背包

0-1背包的定义：

有N件物品和一个容量为V的背包，第i件物品消耗的容量为Ci，价值为Wi，求解放入哪些物品可以使得背包中总价值最大。

基本实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
N // 物品种数，且每种物品只有一件

C = [C1, C2, ... , Cn] // 每件物品对应消耗的容量

W = [W1, W2, ... , Wn] // 每件物品对应的价值

V // 背包容量


const 01Knapsack = (C, W, V) => {
    const N = C.length
    let dp = new Array(V + 1).fill(0)

    for(let i = 0; i < N; i++) {
        for(let j = V; j >= C[i]; j--) {
            dp[j] = max(dp[j], dp[j - C[i]] + W[i])
        }
    }
}

完全背包的定义：

有N种物品和一个容量为V的背包，每种物品都有无限件可用，第i件物品消耗的容量为Ci，价值为Wi，求解放入哪些物品可以使得背包中总价值最大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
N // 物品种数，且每种物品有无限件

C = [C1, C2, ... , Cn] // 每件物品对应消耗的容量

W = [W1, W2, ... , Wn] // 每件物品对应的价值

V // 背包容量


const Knapsack = (C, W, V) => {
    const N = C.length
    let dp = new Array(V + 1).fill(0)

    for(let i = 0; i < N; i++) {
        for(let j = C[i]; j <= V; j++) {
            dp[j] = max(dp[j], dp[j - C[i]] + W[i])
        }
    }
}

4.2 多重背包

思路：先将多重背包转化为0-1背包，再进行相应运算，详见 4 回到需求

上一页
#动态规划 #技术 #算法
下一页