动态规划【DP】详细解释_动态dp

动态规划，英文简称DP，是一种常见的算法设计思想。 它通常被应用于需要求解最优化问题的场景中。其核心思想是将原问题分解成若干个子问题进行求解，并将子问题的解记录下来，避免重复计算。

动态规划的常见四步骤为：定义状态；设计状态转移方程；给定边界条件；利用状态、边界条件和状态转移方程求解原问题。下面我为大家详细解释一下动态规划的这几个步骤。

1. 定义状态

动态规划中，状态是指用来描述问题的一些特征量。这些特征量不断随着问题求解过程中的子问题而变化。刻画状态需要遵循两个原则：最优子结构和无后效性。

最优子结构：原问题的最优解包含了所有子问题的最优解。也就是说，子问题的最优解可以以某种方式推导出原问题的最优解。

无后效性：状态只与其之前的状态有关，和之后的状态无关。这种性质被称作“无后效性”，即在求解阶段，我们不必关心状态是如何转移过来的，只需要关注现在的状态和后续状态。

2. 设计状态转移方程

定义好状态之后，需要将状态之间的联系建立起来，也就是状态转移。这一步骤是动态规划的核心。状态转移方程描述状态转移的数学方程，通常用一个简单的递推式来表达。该递推式的作用是用上一个状态的值来计算当前状态的值。

例如，在背包问题中，我们定义状态$f_{i,j}$表示前$i$个物品中，在背包容量为$j$时所能获得的最大价值。则状态方程可表示为：

$$f_{i,j}=\max (f_{i-1,j},f_{i-1,j-w_i}+v_i)$$

3. 给定边界条件

边界条件是指状态方程中最接近子问题的那些状态的值。它们直接影响到状态转移的过程。设计好边界条件后，状态转移方程就可以按照递推的方式求解了。在大多数情况下，边界条件是初始状态。

4. 利用状态、边界条件和状态转移方程求解原问题

在得到状态转移方程和边界条件之后，我们就可以通过递推的方式求解出原问题了。

动态规划算法的复杂度和空间利用率很高，适用于求解一些比较复杂的最优化问题，例如背包问题、最长递增子序列问题、编辑距离问题等。当然，使用动态规划的前提是需要满足最优子结构和无后效性这两个特点，只有同时满足这两个特点，才能奏效。

好的，举一个具体的例子，就以 Fibonacci 数列为例子，用 LaTeX 语言阐述动态规划的思想和步骤：

在计算 Fibonacci 数列问题中，例如计算斐波那契数列的第 $n$ 项，我们可以使用递归方式求解，在代码实现过程中，会涉及到大量重复计算的问题。例如，我们要计算 Fibonacci 数列中第 $n$ 项的值，常规的递归计算过程中，会反复计算 Fibonacci($n-1$) 和 Fibonacci($n-2$)，这个重复计算的过程也就是动态规划中所说的“重叠子问题”。

因此，我们可以使用动态规划来优化以上过程，摆脱这些重复计算。

（1） 定义状态

对于 Fibonacci 数列问题，我们可以定义状态 $f_i$ 来表示斐波那契数列中第 $i$ 项的值。因为每一项是由前两项相加得到的，所以我们需要知道前两项（$f_{i-1}$ 和 $f_{i-2}$）的值，才能求出第 $i$ 项（$f_i$）的值。因此，状态转移时我们只需要考虑前两项就可以了。

（2） 设计状态转移方程

通过对状态的定义，我们可以设计出状态转移方程：

$$f_i=f_{i-1}+f_{i-2}$$

（3） 给定边界条件

优化递归算法时，我们需要给定边界条件。对于斐波那契数列问题，很容易得到边界条件：

$$f_0=0,f_1=1$$

（4） 利用状态、边界条件和状态转移方程求解原问题

接下来根据状态转移方程和边界条件来求解斐波那契数列中第 $n$ 项的值。 我们可以直接用循环方式计算，从 $f_2$ 开始，依次计算 $f_3,f_4,...,f_n$，并将其存储起来，最终返回 $f_n$ 的结果值。

下面是代码实现：

def fibonacci(n):
    if n <= 1:
        return n
    fib = [0] * (n + 1)
    fib[0], fib[1] = 0, 1
    for i in range(2, n + 1):
        fib[i] = fib[i-1] + fib[i-2]
    return fib[n]
1
2
3
4
5
6
7
8

通过以上步骤及代码实现，我们就可以解决斐波那契数列的问题了。这个例子也直观地阐述了动态规划的思想和步骤。
好的，再举一个十分复杂的例子，以解决旅行家问题为例子，我们来详细介绍动态规划的思想和步骤。

旅行家问题，也就是旅行商问题，是指一个旅行商要在有限的时间内完成对所有城市的旅行，且经过每个城市恰好一次。该问题的解决可以以最短路为关键指标之一。

下面是解决旅行家问题的动态规划的步骤：

（1）定义状态

对于旅行家问题，我们可以定义状态 $f(S,i)$ 表示从起点出发，经过集合 $S$ 中的点，当前在点 $i$ 时的最小代价。

（2）设计状态转移方程

对于 $f(S,i)$，我们可以从集合 $S$ 的子集 $T$ 中的一点 $j$ 转移过来，这样的话，$f(S,i)$ 就可以表示为：

f ( S , i ) = min ⁡ j ∈ T f ( S − { i } , j ) + w j , i f(S,i) = \min_{j \in T}{f(S - \{i\},j) + w_{j,i}} f(S,i)=j∈Tmin​f(S−{i},j)+wj,i​

其中，$w_{j,i}$ 表示从 $j$ 到 $i$ 的代价。

（3）给定边界条件

我们需要给定边界条件，即当集合 $S$ 只有一个点 $i$ 时的代价为 $w_{1,i}$。

f ( { i } , i ) = w 1 , i f(\{i\},i) = w_{1,i} f({i},i)=w1,i​

（4）利用状态、边界条件和状态转移方程求解原问题

依据状态转移方程和边界条件，我们可以得到从起点出发，经过点集 $V$（除去起点）中的所有点恰好一次，回到起点的最小代价，通过循环方式依次求出每一个状态并存储它的最小代价值，最终返回从起点出发，经过点集 $V$ 中的所有点恰好一次，回到起点的最小代价。

下面是满足以上要求的旅行家问题的代码实现：

def tsp(n, m, w):
    f = [[math.inf] * n for _ in range(1 << (n-1))]
    f[1][0] = 0
    for S in range(1, 1 << (n-1)):
        for i in range(1, n):
            if S & (1 << (i-1)):
                for j in range(1, n):
                    if S - (1 << (i-1)) == 1 << (j-1):
                        f[S][i] = w[0][i]
                    if (S & (1 << (j-1))) and j != i:
                        f[S][i] = min(f[S][i], f[S ^ (1 << (i-1))][j] + w[j][i])
    ans = math.inf
    for i in range(1, n):
        ans = min(ans, f[(1 << (n-1))-1][i] + w[i][0])
    return ans

n, m = map(int, input().split())
w = [[math.inf] * n for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    w[a-1][b-1] = w[b-1][a-1] = c
print(tsp(n, m, w))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

总的来说，动态规划可以解决很多复杂问题，例如最长公共子序列问题、最优二叉搜索树问题等。通过以上例子及步骤，我们更好地理解了动态规划的思想和实现方法。