动态规划（Dynamic Programming）

Posted on 2022-01-19 Edited on 2022-04-22 In algorithm Views:

动态规划（Dynamic Programming）是一种通过将最优问题分解为更简单的子问题，并利用了整体问题的最优解取决于其子问题的最优解这一事实来解决最优问题的算法技术。动态规划中的“Programming”指的是表格法，而非编写代码。

动态规划

动态规划的特征

最优子结构(Optimal Substructure)

问题的最优解可以通过相关子问题的最优解组合而成，而这些子问题可以独立求解。
重复子问题
无后效性

动态规划的求解方法

自底向上的表格法(Bottom-up with Tabulation)

自顶向下法的记忆式方法(Top-down with Memoization)

动态规划问题

问题1

问题描述，如下图：

x轴代表时间轴；
每个长方型代表不同的任务；任务横跨时间格，表示完成该任务所需要的时间；完成任务可以获取相应收入；
假设任务不能同时进行，求解最大收入？

这是一个寻找最优解的问题，我们假设$OPT(i)$表示截至任务$i$的最优解，$v_i$表示完成任务$i$获得的收入，$prev(i)$表示任务$i$最邻近的前置可选择任务。

从最后一个任务开始分析，对于第8个任务，可以选择做或不做：如果选择做任务8，那么从上图可以看出只能选择任务5以及前面的任务，截至任务5的最优解可以记为$OPT(5)$，那么$OPT(8)=OPT(5)+v_8$；如果选择不做任务8，那么$OPT(8)=OPT(7)$；所以我们只需要取$OPT(5)+v_8$和$OPT(7)$中的较大者，于是可以写成：$OPT(8) = max\begin{cases}选\ \ \ ：OPT(prev(8))+v_8 \\不选：OPT(7)\end{cases}$

于是，我们得到了该最优化问题的推导式：
$$
OPT(i) = max
\begin{cases}
选\ \ \ ：OPT(prev(i))+v_i \\
\ \\
不选：OPT(i-1)
\end{cases}
$$
依据推导式，该问题的展开图如下，图中相同颜色标识了重叠子问题：

依次带入上图，我们可以得到如下最优解表格，最终任务8对应的最优方案就是本题的最优解：

任务项	prev(i)	OPT(i)	最优方案
1	0	5	1($5)
2	0	5	1($5)
3	0	8	3($8)
4	1	9	1(\$5)、4(\$4)
5	0	9	1(\$5)、4(\$4)
6	2	9	1(\$5)、4(\$4)
7	3	10	3(\$8)、7(\$2)
8	5	13	1(\$5)、4(\$4)、8(\$4)

代码如下：

# 任务对应的收入
arr = [5, 1, 8, 4, 6, 3, 2, 4]
# 前置任务
prev = [-1, -1, -1, 0, -1, 1, 2, 4]

def dp_opt():
    opt = [0]*len(arr)

    # 出口
    opt[0] = arr[0]
    opt[1] = max(arr[0], arr[1])

    for n in range(2, len(arr)):
        if prev[n] == -1:  # 没有前置任务
            A = arr[n]  # 选
            B = opt[n-1]  # 不选
            opt[n] = max(A, B)
        else:
            A = opt[prev[n]] + arr[n]  # 选
            B = opt[n-1]  # 不选
            opt[n] = max(A, B)

    return opt[-1]  # opt最后元素作为最优解

问题2

问题描述：求如下数值数组中，不相邻数值之和的最大值？

这是一个寻找最优解的问题，我们假设$OPT(i)$表示截至索引$i$的最优解。

从最后一个数值分析，对于索引6的数值，可以选或不选：如果选，那么随后只能选不相邻的索引4的数值，截至索引4的最优解可以记为$OPT(4)$，那么$OPT(6)=OPT(4)+arr[6]$；如果不选，那么$OPT(6)=OPT(5)$；所以我们只需要取$OPT(4)+arr[6]$和$OPT(5)$中的较大者，于是可以写成：$OPT(6) = max\begin{cases}选\ \ \ ：OPT(4)+arr[6] \\不选：OPT(5)\end{cases}$

于是，我们得到了该最优化问题的推导式：
$$
OPT(i) = max
\begin{cases}
选\ \ \ ：OPT(i-2)+arr[i] \\
\ \\
不选：OPT(i-1)
\end{cases}
$$
依据推导式，该问题的展开图如下，图中相同颜色标识了重叠子问题：

依次带入上图，我们可以得到如下最优解表格，最终索引6对应的最优和就是本题的最优解：

索引	OPT(i)	最优方案
0	1	arr[0]
1	2	arr[1]
2	5	arr[0]+arr[2]
3	5	arr[0]+arr[2]
4	12	arr[0]+arr[2]+arr[4]
5	12	arr[0]+arr[2]+arr[4]
6	15	arr[0]+arr[2]+arr[4]+arr[6]

代码如下：

arr = [1, 2, 4, 1, 7, 8, 3]

def dp_opt():
    opt = [0] * len(arr)

    # 出口
    opt[0] = arr[0]
    opt[1] = max(arr[0], arr[1])

    for n in range(2, len(arr)):
            A = opt[n-2] + arr[n]  # 选
            B = opt[n-1]  # 不选
            opt[n] = max(A, B)

    return opt[-1]  # opt最后元素作为最优解

对应的递归代码如下：

arr = [1, 2, 4, 1, 7, 8, 3]

def rec_opt(arr, i):
    if i == 0:
        return arr[0]
    elif i == 1:
        return max(arr[0], arr[1])
    else:
        A = rec_opt(arr, i - 2) + arr[i]  # 选
        B = rec_opt(arr, i - 1)  # 不选
        return max(A, B)

问题3

问题描述：如下数组中是否存在相加之和等于9的组合？

我们假设$Subset(arr[i], S)$表示截至索引$i$的解。

从最后一个数值分析，对于索引5的数值，可以选或不选：如果选，那么随后只需要找索引4前是否能找到和为7的组合，即$Subset(4, 7)$；如果不选，那么随后需要找索引4前是否能找到和为9的组合，即$Subset(4, 9)$，于是可以写成：$Subset(5, 9) = or\begin{cases}选\ \ \ ：Subset(4, 7) \\不选：Subset(4, 9)\end{cases}$

于是，我们得到了该最优化问题的推导式：
$$
Subset(i, S) = or
\begin{cases}
选\ \ \ ：Subset(i-1, S-arr[i]) \\
\ \\
不选：Subset(i-1, S)
\end{cases}
$$
依据推导式，该问题的展开图如下（图中只给出了部分展开形式）：

其中，上图中有颜色的节点为三类程序出口点：

第一类，蓝色$Subset(0, 9) $：$i=0$表示数组arr再无任何前置数据，所以$Subset(0, 9)=\begin{cases}False，当arr[0] \neq 9，\\True，当arr[0]=9\end{cases}$；
第二类，黄色$Subset(1, 0) $：$S=0$时，任何$Subset(i, 0)=True$，因为无需选择任何数值就满足要求；
第二类，粉色$Subset(2, -3)、Subset(2, -8)、Subset(0, -15)$：$S<0$表示不能选择该选项，只能选择另外的选项；

根据上面的分析，我们构造并填入下面的表格，其中：每行代表原数组$arr$索引，每列表示和$S$，于是每个单元格$Subset(i, S)$表示是否存在能找到和为$S$的组合，为布尔类型：

首先填表中第一行，我们分析$i=0时，Subset(0, S) = \begin{cases}False，当arr[i] \neq S \\True，当arr[i]=S\end{cases}$；
然后填表中第一列，$S=0时，为True$；
再然后，我们依次填入第2行、第3行、…、第6行；
最后一行中的最后一列为最后的解；

			S
arr[i]	值	索引	0	1	2	3	4	5	6	7	8	9
	3	0	F	F	F	T	F	F	F	F	F	F
	34	1	T
	4	2	T
	12	3	T
	5	4	T
	2	5	T

代码如下：

import numpy as np

arr = [3, 34, 4, 12, 5, 2]

def dp_subset(S):
    subset = np.zeros((len(arr), S+1), dtype=bool)

    # 出口1
    subset[:, 0] = True  # 第一列全部置为True

    # 出口2
    subset[0, :] = False  # 第一行全部置为False
    subset[0, arr[0]] = True  # 第一行中，S=arr[0]的单元格置为False

    for i in range(1, len(arr)):
        for s in range(1, S+1):
            if arr[i] > s:
                subset[i, s] = subset[i-1, s]
            else:
                A = subset[i-1, s-arr[i]]  # 选
                B = subset[i-1, s]  # 不选
                subset[i, s] = A or B

    return subset[-1, -1]  # subset最后元素作为解

print(dp_subset(9))

对应的递归代码如下：

arr = [3, 34, 4, 12, 5, 2]

def rec_subset(arr, i, s):
    if s == 0:
        return True
    elif i == 0:
        return arr[i] == s
    elif arr[i] > s:
        return rec_subset(arr, i-1, s)
    else:
        A = rec_subset(arr, i-1, s-arr[i])  # 选
        B = rec_subset(arr, i-1, s)  # 不选
        return A or B

print(rec_subset(arr, len(arr)-1, 9))

jtLiBrain

动态规划（Dynamic Programming）

动态规划

动态规划的特征

动态规划的求解方法

自底向上的表格法(Bottom-up with Tabulation)

自顶向下法的记忆式方法(Top-down with Memoization)

动态规划问题

问题1

问题2

问题3

参考