动态规划 实例

动态规划 实例

一、数字三角形（树形动规）

				7
			  3   8
		    8   1   0
		  2   7   4   4
	    4   5   2   6   5
1
2
3
4
5

在数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可，不必给出具体路径。 三角形的行数大于 1 小于等于 100，数字为 0 - 99 。

输入格式：

5      // 表示三角形的行数    接下来输入三角形
7
3   8
8   1   0
2   7   4   4
4   5   2   6   5
1
2
3
4
5
6

要求输出最大和
n = 5

用二维列表来存放数字三角形
d = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]

maxSum(i, j) 表示从 d[i][j] 到底边的各条路径中，最佳路径的数字之和。
此题的最终问题就变成了求 maxSum(0,0)

1、简单的递归

d[i][j] 出发，下一步只能走 d[i + 1][j] 或者 d[i + 1][j+1] 。

def maxSum(i, j):
    if i == n-1:
        return d[i][j] # 最下面一行，边界
    else:
        return d[i][j] + max(maxSum(i + 1, j), maxSum(i + 1, j + 1))


n = 5
d = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
print(max_sum(0, 0))
1
2
3
4
5
6
7
8
9
10

代码运行超时，为什么会超时呢？
重复计算，每个数遍历的次数：

就拿第三行数字 1 来说，当我们计算从第 2 行的数字 3 开始的 maxSum(1,0) 时会计算出从 1 开始的 maxSum(2,1)，当计算从第二行的数字 8 开始的 maxSum(1, 1) 的时候又会计算一次从 1 开始的 maxSum(1, 1)。也就是说采用递归的方法，深度遍历每条路径，存在大量重复计算。则时间复杂度为 2 的 n 次方，对于 n = 100 行，肯定超时。

如何改进，如果每算出一个 maxSum(i, j) 就保存起来，下次用到其值的时候直接取用，则可免去重复计算。那么可以用 n 方的时间复杂度完成计算。因为三角形的数字总数是 n(n + 1) // 2

2、记忆递归型的动态规划

def maxSum(i, j):
    if m[i][j] != -1:
        return m[i][j]
    elif i == n - 1:
        m[i][j] = d[i][j]
    else:
        x = maxSum(i + 1, j)
        y = maxSum(i + 1, j + 1)
        m[i][j] = max(x, y) + d[i][j]

    return m[i][j]


n = 5
d = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
m = [[-1 for j in range(i + 1)] for i in range(n)]

print(m)
print(maxSum(0, 0))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
'
运行
运行

递归总是需要使用大量堆栈上的空间，很容易造成栈溢出，现在就要考虑如何把递归转换为递推。

首先需要计算的是最后一行，因此可以把最后一行直接写出，如下图：

现在开始分析倒数第二行的每一个数，数字 2，2 可以和最后一行 4 相加，也可以和最后一行的 5 相加，但是很显然和 5 相加要更大一点，结果为 7，我们此时就可以将 7 保存起来，然后分析数字 7，7 可以和最后一行的5相加，也可以和最后一行的 2 相加，很显然和 5 相加更大，结果为 12，因此我们将 12 保存起来。以此类推。我们可以得到下面这张图：

以依次类推得到如下结果：

2、递推型动态规划

n = 5
d = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]

import copy
m = copy.deepcopy(d)
if n > 1:
	# 从倒数第二行开始
	for i in range(n-2,-1,-1):
	    for j in range(i+1):
	        m[i][j] = d[i][j]+max(m[i+1][j],m[i+1][j+1])

print(m[0][0])

# 直接在d上做即可
if n > 1:
	for i in range(n-2,-1,-1):
	    for j in range(i+1):
	        d[i][j] = d[i][j] + max(d[i+1][j], d[i+1][j+1])

print(d[0][0])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
'
运行
运行

对空间进行优化，其实完全没必要用二维列表 m 存储每一个 maxSum(i,j)，只要从底层一行行向上递推，那么只要一维列表 maxSum 即可，即只要存储一行的 maxSum 值就可以。

对于空间优化后的具体递推过程如下：

进一步考虑，我们甚至可以连 maxSum 列表都可以不要，直接用 d 的第 n 行直接替代 maxSum 即可。但是这里需要强调的是：虽然节省空间，但是时间复杂度还是不变的。

依照上面的方式，我们可以写出如下代码：

n = 5
d = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]

maxSum = d[n - 1] # maxSum 指向第 n 行  

for i in range(n - 2, -1, -1):     
    for j in range(i + 1):       
        maxSum[j] = max(maxSum[j], maxSum[j+1]) + d[i][j] 

print(maxSum)
print(d) # 注意 d 的最后一行也被修改
1
2
3
4
5
6
7
8
9
10
11
'
运行
运行

总结：

递归到动规的一般转化方法

递归函数有 n 个参数，就定义一个 n 维的数组，数组的下标是递归函数参数的取值范围，数组元素的值是递归函数的返回值，这样就可以从边界值开始， 逐步填充数组，相当于计算递归函数值的逆过程。

动规解题的一般思路

1、将原问题分解为子问题

把原问题分解为若干个子问题，子问题和原问题形式相同或类似，只不过规模变小了。子问题都解决，原问题即解决(数字三角形例）。
子问题的解一旦求出就会被保存，所以每个子问题只需求 解一次。

2、确定状态

在用动态规划解题时，我们往往将和子问题相关的各个变量的一组取值，称之为一个“状 态”。一个“状态”对应于一个或多个子问题， 所谓某个“状态”下的“值”，就是这个“状 态”所对应的子问题的解。
所有“状态”的集合，构成问题的“状态空间”。“状态空间”的大小，与用动态规划解决问题的时间复杂度直接相关。 在数字三角形的例子里，一共有N×(N+1)/2个数字，所以这个问题的状态空间里一共就有N×(N+1)/2个状态。
整个问题的时间复杂度是状态数目乘以计算每个状态所需时间。在数字三角形里每个“状态”只需要经过一次，且在每个状态上作计算所花的时间都是和N无关的常数。

3、确定一些初始状态（边界状态）的值

以“数字三角形”为例，初始状态就是底边数字，值就是底边数字值。

4、确定状态转移方程

定义出什么是“状态”，以及在该“状态”下的“值”后，就要找出不同的状态之间如何迁移――即如何从一个或多个“值”已知的 “状态”，求出另一个“状态”的“值”(递推型)。状态的迁移可以用递推公式表示，此递推公式也可被称作“状态转移方程”。

能用动规解决的问题的特点

1) 问题具有最优子结构性质。如果问题的最优解所包含的 子问题的解也是最优的，我们就称该问题具有最优子结 构性质。
2) 无后效性。当前的若干个状态值一旦确定，则此后过程的演变就只和这若干个状态的值有关，和之前是采取哪种手段或经过哪条路径演变到当前的这若干个状态，没有关系。
1
2

a=[[1],[1,2]]
b=a # 赋值引用
b=a[:] # 浅拷贝
b=a.copy() # 浅拷贝
b=(__import__('copy').deepcopy(a)) # 深拷贝
print(a is b)
print(a[0] is b[0])
print(a[1] is b[1])
1
2
3
4
5
6
7
8
'
运行
运行

二、石子游戏 LeetCode

几块石子 排成一行 ，每块石子都有一个关联值，关联值为整数，由数组 stoneValue 给出。

游戏中的每一轮：Alice 会将这行石子分成两个 非空行（即，左侧行和右侧行）；Bob 负责计算每一行的值，即此行中所有石子的值的总和。Bob 会丢弃值最大的行，Alice 的得分为剩下那行的值（每轮累加）。如果两行的值相等，Bob 让 Alice 决定丢弃哪一行。下一轮从剩下的那一行开始。

只 剩下一块石子 时，游戏结束。Alice 的分数最初为 0 。

返回 Alice 能够获得的最大分数 。

示例 1：

输入：stoneValue = [6,2,3,4,5,5]
输出：18
解释：在第一轮中，Alice 将行划分为 [6，2，3]，[4，5，5] 。左行的值是 11 ，右行的值是 14 。Bob 丢弃了右行，Alice 的分数现在是 11 。
在第二轮中，Alice 将行分成 [6]，[2，3] 。这一次 Bob 扔掉了左行，Alice 的分数变成了 16（11 + 5）。
最后一轮 Alice 只能将行分成 [2]，[3] 。Bob 扔掉右行，Alice 的分数现在是 18（16 + 2）。游戏结束，因为这行只剩下一块石头了。

示例 2：

输入：stoneValue = [7,7,7,7,7,7,7]
输出：28

示例 3：

输入：stoneValue = [4]
输出：0

方法一：动态规划

我们用 f[l][r] 表示当 Alice 面对数组 stoneValue 中从位置 l 到 r 这一段连续的石子时，她能获得的最大分数。

由于 Alice 需要选择将这一段石子分成两部分，因此我们可以枚举分隔位置 i，左侧部分的石子从位置 l 到 i，右侧部分的石子从位置 i+1 到 r。记 sum(l,r) 表示位置 l 到 r 的石子的分数之和，根据题目要求：

如果 sum(l,i)<sum(i+1,r)，那么 Bob 会丢弃右侧部分，状态转移方程为：

f[l][r]=f[l][i]+sum(l,i)

如果 sum(l,i)>sum(i+1,r)，那么 Bob 会丢弃左侧部分，状态转移方程为：

f[l][r]=f[i+1][r]+sum(i+1,r)

如果 sum(l,i)=sum(i+1,r)，那么 Bob 会让 Alice 选择丢弃的部分，状态转移方程为：

f[l][r]=max{f[l][i],f[i+1][r]}+sum(l,i)

我们可以预先计算出 sum(l,r) 的值，可以使用前缀和或直接遍历计算的方法。在枚举 i 时，我们可以同时计算出 sum(l,i) 的值，这样sum(i+1,r) 的值就可以通过

sum(i+1,r)=sum(l,r)−sum(l,i)

在 O(1) 的时间得出。

当只剩下一颗石子时，Alice 的得分为 00，对应的边界条件为：

f[l][l]=0

最终的答案即为 f[0][n-1]f[0][n−1]，其中 nn 是数组 \textit{stoneValue}stoneValue 的长度。

注意：如果使用三重循环枚举 ll，rr，ii 进行状态转移，那么 C++ 语言的代码可能会超出时间限制。因此下面给出的代码使用了自顶向下的记忆化搜索方法来完成动态规划。这样可以跳过一部分无需计算的状态，并在合理的时间内通过本题。

class Solution:
    def stoneGameV(self, stoneValue: List[int]) -> int:
        @lru_cache(None)
        def dfs(left: int, right: int) -> int:
            if left == right:
                return 0
            
            total = sum(stoneValue[left:right+1])
            suml = ans = 0
            for i in range(left, right):
                suml += stoneValue[i]
                sumr = total - suml
                if suml < sumr:
                    ans = max(ans, dfs(left, i) + suml)
                elif suml > sumr:
                    ans = max(ans, dfs(i + 1, right) + sumr)
                else:
                    ans = max(ans, max(dfs(left, i), dfs(i + 1, right)) + suml)
            return ans
        
        n = len(stoneValue)
        return dfs(0, n - 1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

复杂度分析

时间复杂度：O(n^3)O(n
3
)，其中 nn 是数组 \textit{stoneValue}stoneValue 的长度。

空间复杂度：O(n^2)O(n
2
)，为存储所有状态需要的空间。

方法二：动态规划优化

本方法为进阶方法，但无需高级的优化技巧，感兴趣的读者可以尝试学习。

考虑某次状态转移中的 ll，rr，ii，如果 \textit{sum}(l, i) < \textit{sum}(i+1, r)sum(l,i)<sum(i+1,r)，那么有状态转移方程：

f[l][r] = f[l][i] + \textit{sum}(l, i)
f[l][r]=f[l][i]+sum(l,i)

而对于 r+1r+1 而言，\textit{sum}(l, i) < \textit{sum}(i+1, r+1)sum(l,i)<sum(i+1,r+1) 一定也成立，那么有状态转移方程：

f[l][r+1] = f[l][i] + \textit{sum}(l, i)
f[l][r+1]=f[l][i]+sum(l,i)

可以发现这两个状态转移方程的右侧相同，f[l][i] + \textit{sum}(l, i)f[l][i]+sum(l,i) 被重复计算，这也是方法一的瓶颈所在。因此，我们可以考虑维护两个辅助数组 \textit{maxl}maxl 和 \textit{maxr}maxr：

\left {

$$\begin{aligned} \textit{maxl}[l][r] &= \max_{i=l}^r \big{ f[l][i] + \textit{sum}(l, i) \big} \ \ \textit{maxr}[l][r] &= \max_{i=l}^r \big{ f[i][r] + \textit{sum}(i, r) \big} \end{aligned}$$ \right.​

maxl[l][r]
maxr[l][r]
​

=
i=l
max
r
​
{f[l][i]+sum(l,i)}

i=l
max
r
​
{f[i][r]+sum(i,r)}
​

这样一来，对于任意的 ll，rr，存在 i_0 \in [l-1, r)i
0
​
∈[l−1,r) 满足：

\left {

$$\begin{aligned} & \textit{sum}(l, i_0) \leq \textit{sum}(i_0+1, r) \ & \textit{sum}(l, i_0+1) > \textit{sum}(i_0+2, r) \end{aligned}$$ \right.
{
​

sum(l,i
0
​
)≤sum(i
0
​
+1,r)
sum(l,i
0
​
+1)>sum(i
0
​
+2,r)
​

其中 \textit{sum}(x, y)sum(x,y) 在 x > yx>y 时的值为 00。

那么当 i \leq i_0i≤i
0
​
时，对应的状态转移方程合并在一起即为：

f[l][r] = \textit{maxl}[l][i_0]
f[l][r]=maxl[l][i
0
​
]

当 i > i_0i>i
0
​
时，对应的状态转移方程合并在一起即为：

f[l][r] = \textit{maxr}[i_0+2][r]
f[l][r]=maxr[i
0
​
+2][r]

特别地，如果 \textit{sum}(l, i_0) = \textit{sum}(i_0+1, r)sum(l,i
0
​
)=sum(i
0
​
+1,r)，还可以有额外的转移：

f[l][r] = \textit{maxr}[i_0+1][r]
f[l][r]=maxr[i
0
​
+1][r]

因此，如果我们知道数组 \textit{maxl}maxl，数组 \textit{maxr}maxr 以及 i_0i
0
​
，那么就可以在 O(1)O(1) 的时间计算出 f[l][r]f[l][r]，完成状态转移。那么我们如何计算出这些需要的信息呢？

细节

观察数组 \textit{maxl}maxl 和 \textit{maxr}maxr 的表示，它提示我们可以使用递推的方法，在枚举 ll，rr 并计算 f[l][r]f[l][r] 的同时，计算出 \textit{maxl}[l][r]maxl[l][r] 和 \textit{maxr}[l][r]maxr[l][r]：

\left {

$$\begin{aligned} \textit{maxl}[l][r] &= \max { \textit{maxl}[l][r-1], f[l][r] + \textit{sum}(l, r) } \ \textit{maxr}[l][r] &= \max { \textit{maxr}[l+1][r], f[l][r] + \textit{sum}(i, r) } \end{aligned}$$ \right.
{
maxl[l][r]
maxr[l][r]
​

=max{maxl[l][r−1],f[l][r]+sum(l,r)}
=max{maxr[l+1][r],f[l][r]+sum(i,r)}
​

边界条件为：

\textit{maxl}[l][l] = \textit{maxr}[l][l] = \textit{stoneValue}[l]
maxl[l][l]=maxr[l][l]=stoneValue[l]

而对于 i_0i
0
​
，记 i_{l,r}i
l,r
​
表示在枚举 ll，rr 时 i_0i
0
​
的值，由于数组 \textit{stoneValue}stoneValue 中所有的数都是正整数，那么有

i_{l,r} \leq i_{l,r+1}
i
l,r
​
≤i
l,r+1
​

即固定 ll，i_{l,r}i
l,r
​
是单调递增的。因此我们可以递减地枚举 ll 并且（在固定 ll 时）递增地枚举 rr，同时维护 i_{l,r}i
l,r
​
：

i_{l,r}i
l,r
​
的初始值为 i_{l,l} = l-1i
l,l
​
=l−1；

当我们已知 i_{l,r}i
l,r
​
时，要求出 i_{l,r+1}i
l,r+1
​
，我们只需不断地增加 i_{l,r}i
l,r
​
，直到 \textit{sum}(l, i_{l,r}) \leq \textit{sum}(i_{l,r}+1, r+1)sum(l,i
l,r
​
)≤sum(i
l,r
​
+1,r+1) 不满足为止。此时 i_{l,r+1}i
l,r+1
​
的值就为 i_{l,r} - 1i
l,r
​
−1。

这样一来，计算 \textit{maxl}[l][r]maxl[l][r] 和 \textit{maxr}[l][r]maxr[l][r] 的时间为 O(1)O(1)，计算 i_0i
0
​
的时间为均摊 O(1)O(1)，我们就可以在 O(1)O(1) 的时间计算出 f[l][r]f[l][r] 了。

代码

class Solution:
def stoneGameV(self, stoneValue: List[int]) -> int:
n = len(stoneValue)
f = [[0] * n for _ in range(n)]
maxl = [[0] * n for _ in range(n)]
maxr = [[0] * n for _ in range(n)]

    for left in range(n - 1, -1, -1):
        maxl[left][left] = maxr[left][left] = stoneValue[left]
        total = stoneValue[left]
        suml = 0
        i = left - 1
        for right in range(left + 1, n):
            total += stoneValue[right]
            while i + 1 < right and (suml + stoneValue[i + 1]) * 2 <= total:
                suml += stoneValue[i + 1]
                i += 1
            if left <= i:
                f[left][right] = max(f[left][right], maxl[left][i])
            if i + 1 < right:
                f[left][right] = max(f[left][right], maxr[i + 2][right])
            if suml * 2 == total:
                f[left][right] = max(f[left][right], maxr[i + 1][right])
            maxl[left][right] = max(maxl[left][right - 1], total + f[left][right])
            maxr[left][right] = max(maxr[left + 1][right], total + f[left][right])
    
    return f[0][n - 1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20