动态规划,英文简称DP,是一种常见的算法设计思想。 它通常被应用于需要求解最优化问题的场景中。其核心思想是将原问题分解成若干个子问题进行求解,并将子问题的解记录下来,避免重复计算。
动态规划的常见四步骤为:定义状态;设计状态转移方程;给定边界条件;利用状态、边界条件和状态转移方程求解原问题。下面我为大家详细解释一下动态规划的这几个步骤。
- 定义状态
动态规划中,状态是指用来描述问题的一些特征量。这些特征量不断随着问题求解过程中的子问题而变化。刻画状态需要遵循两个原则:最优子结构和无后效性。
最优子结构:原问题的最优解包含了所有子问题的最优解。也就是说,子问题的最优解可以以某种方式推导出原问题的最优解。
无后效性:状态只与其之前的状态有关,和之后的状态无关。这种性质被称作“无后效性”,即在求解阶段,我们不必关心状态是如何转移过来的,只需要关注现在的状态和后续状态。
- 设计状态转移方程
定义好状态之后,需要将状态之间的联系建立起来,也就是状态转移。这一步骤是动态规划的核心。状态转移方程描述状态转移的数学方程,通常用一个简单的递推式来表达。该递推式的作用是用上一个状态的值来计算当前状态的值。
例如,在背包问题中,我们定义状态 f i , j f_{i,j} fi,j表示前 i i i个物品中,在背包容量为 j j j时所能获得的最大价值。则状态方程可表示为:
f i , j = max ( f i − 1 , j , f i − 1 , j − w i + v i ) f_{i,j} = \max(f_{i-1,j},f_{i-1,j-w_{i}}+v_{i}) fi,j=max(fi−1,j,fi−1,j−wi+vi)
- 给定边界条件
边界条件是指状态方程中最接近子问题的那些状态的值。它们直接影响到状态转移的过程。设计好边界条件后,状态转移方程就可以按照递推的方式求解了。在大多数情况下,边界条件是初始状态。
- 利用状态、边界条件和状态转移方程求解原问题
在得到状态转移方程和边界条件之后,我们就可以通过递推的方式求解出原问题了。
动态规划算法的复杂度和空间利用率很高,适用于求解一些比较复杂的最优化问题,例如背包问题、最长递增子序列问题、编辑距离问题等。当然,使用动态规划的前提是需要满足最优子结构和无后效性这两个特点,只有同时满足这两个特点,才能奏效。
好的,举一个具体的例子,就以 Fibonacci 数列为例子,用 LaTeX 语言阐述动态规划的思想和步骤:
在计算 Fibonacci 数列问题中,例如计算斐波那契数列的第 n n n 项,我们可以使用递归方式求解,在代码实现过程中,会涉及到大量重复计算的问题。例如,我们要计算 Fibonacci 数列中第 n n n 项的值,常规的递归计算过程中,会反复计算 Fibonacci( n − 1 n-1 n−1) 和 Fibonacci( n − 2 n-2 n−2),这个重复计算的过程也就是动态规划中所说的“重叠子问题”。
因此,我们可以使用动态规划来优化以上过程,摆脱这些重复计算。
(1) 定义状态
对于 Fibonacci 数列问题,我们可以定义状态 f i f_i fi 来表示斐波那契数列中第 i i i 项的值。因为每一项是由前两项相加得到的,所以我们需要知道前两项( f i − 1 f_{i-1} fi−1 和 f i − 2 f_{i-2} fi−2)的值,才能求出第 i i i 项( f i f_{i} fi)的值。因此,状态转移时我们只需要考虑前两项就可以了。
(2) 设计状态转移方程
通过对状态的定义,我们可以设计出状态转移方程:
f i = f i − 1 + f i − 2 f_i = f_{i-1} + f_{i-2} fi=fi−1+fi−2
(3) 给定边界条件
优化递归算法时,我们需要给定边界条件。对于斐波那契数列问题,很容易得到边界条件:
f 0 = 0 , f 1 = 1 f_0 = 0, f_1 = 1 f0=0,f1=1
(4) 利用状态、边界条件和状态转移方程求解原问题
接下来根据状态转移方程和边界条件来求解斐波那契数列中第 n n n 项的值。 我们可以直接用循环方式计算,从 f 2 f_2 f2 开始,依次计算 f 3 , f 4 , . . . , f n f_3, f_4, ..., f_n f3,f4,...,fn,并将其存储起来,最终返回 f n f_n fn 的结果值。
下面是代码实现:
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)定义状态
对于旅行家问题,我们可以定义状态 f ( S , i ) f(S,i) f(S,i) 表示从起点出发,经过集合 S S S 中的点,当前在点 i i i 时的最小代价。
(2)设计状态转移方程
对于 f ( S , i ) f(S,i) f(S,i),我们可以从集合 S S S 的子集 T T T 中的一点 j j j 转移过来,这样的话, f ( S , i ) f(S,i) 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∈Tminf(S−{i},j)+wj,i
其中, w j , i w_{j,i} wj,i 表示从 j j j 到 i i i 的代价。
(3)给定边界条件
我们需要给定边界条件,即当集合 S S S 只有一个点 i i i 时的代价为 w 1 , i w_{1,i} w1,i。
f ( { i } , i ) = w 1 , i f(\{i\},i) = w_{1,i} f({i},i)=w1,i
(4)利用状态、边界条件和状态转移方程求解原问题
依据状态转移方程和边界条件,我们可以得到从起点出发,经过点集 V V V(除去起点)中的所有点恰好一次,回到起点的最小代价,通过循环方式依次求出每一个状态并存储它的最小代价值,最终返回从起点出发,经过点集 V V V 中的所有点恰好一次,回到起点的最小代价。
下面是满足以上要求的旅行家问题的代码实现:文章来源:https://www.toymoban.com/news/detail-751834.html
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))
总的来说,动态规划可以解决很多复杂问题,例如最长公共子序列问题、最优二叉搜索树问题等。通过以上例子及步骤,我们更好地理解了动态规划的思想和实现方法。文章来源地址https://www.toymoban.com/news/detail-751834.html
到了这里,关于动态规划【DP】详细解释的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!