动态规划【DP】详细解释

这篇具有很好参考价值的文章主要介绍了动态规划【DP】详细解释。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

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

  1. 定义状态

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

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

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

  1. 设计状态转移方程

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

例如,在背包问题中,我们定义状态 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(fi1,j,fi1,jwi+vi)

  1. 给定边界条件

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

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

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

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

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

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

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

(1) 定义状态

对于 Fibonacci 数列问题,我们可以定义状态 f i f_i fi 来表示斐波那契数列中第 i i i 项的值。因为每一项是由前两项相加得到的,所以我们需要知道前两项( f i − 1 f_{i-1} fi1 f i − 2 f_{i-2} fi2)的值,才能求出第 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=fi1+fi2

(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)=jTminf(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 中的所有点恰好一次,回到起点的最小代价。

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

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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 动态规划(DP)(算法笔记)

    本文内容基于《算法笔记》和官方配套练题网站“晴问算法”,是我作为小白的学习记录,如有错误还请体谅,可以留下您的宝贵意见,不胜感激。 动态规划(Dynamic Programming,DP)是一种用来解决一类最优化问题的算法思想。简单来说,动态规划将一个复杂的问题分解成若干个子

    2024年02月05日
    浏览(44)
  • acwing算法基础之动态规划--线性DP和区间DP

    线性DP:状态转移表达式存在明显的线性关系。 区间DP:与顺序有关,状态与区间有关。 题目1 :数字三角形。 解题思路:直接DP即可, f[i][j] 可以来自 f[i-1][j] + a[i][j] 和 f[i-1][j-1] + a[i][j] ,注意 f[i-1][j] 不存在的情况(最后一个点)和 f[i-1][j-1] 不存在的情况(第一个点)。

    2024年02月04日
    浏览(49)
  • 石子合并(动态规划 区间DP)+详细注释

    原题链接   活动 - AcWing 题目 设有 N 堆石子排成一排,其编号为 1,2,3,…,N。 每堆石子有一定的质量,可以用一个整数来描述,现在要将这 N 堆石子合并成为一堆。 每次只能合并相邻的两堆,合并的代价为这两堆石子的质量之和,合并后与这两堆石子相邻的石子将和新堆相

    2024年02月16日
    浏览(38)
  • C++动态规划-线性dp算法

    莫愁千里路 自有到来风 CSDN 请求进入专栏                                    X 是否进入《 C++ 专栏》? 确定 目录  线性dp简介 斐波那契数列模型  第N个泰波那契数 思路: 代码测试:  三步问题 思路: 代码测试: 最小花费爬楼梯 思路: 代码测试:  路径问题 数字三

    2024年02月19日
    浏览(46)
  • 【算法】动态规划(dp问题),持续更新

    介绍本篇之前,我想先用人话叙述一般解决动态规划问题的思路: 动态规划的问题,本身有许多产生结果的可能,需要在具体题目下得到满足某个条件的解。 如何得到呢? 我们就需要根据这个具体问题,建立一个状态表( dp 表 ),在这张 dp 表中的每一个位置的数据都有明

    2024年02月04日
    浏览(48)
  • AcWing算法学习笔记:动态规划(背包 + 线性dp + 区间dp + 计数dp + 状态压缩dp + 树形dp + 记忆化搜索)

    算法 复杂度 时间复杂度0(nm) 空间复杂度0(nv) 代码 算法 通过滚动数组对01背包朴素版进行空间上的优化 f[i] 与 f[i - 1]轮流交替 若体积从小到大进行遍历,当更新f[i, j]时,f[i - 1, j - vi] 已经在更新f[i, j - vi]时被更新了 因此体积需要从大到小进行遍历,当更新f[i, j]时,f[i - 1,

    2024年02月21日
    浏览(42)
  • 算法套路十三——动态规划DP入门

    动态规划和递归都是通过将大问题分解为较小的子问题来解决问题。它们都可以用来解决具有重叠子问题和最优子结构特性的问题。 递归是一种自顶向下的方法, 它从原始问题开始 ,递归地将问题分解为较小的子问题dfs(i)—— dfs(i)代表的是从第i个状态开始进行递归求解能

    2024年02月15日
    浏览(57)
  • c++ 算法之动态规划—— dp 详解

    dp 是 c++ 之中一个简单而重要的算法,每一个 OIer 必备的基础算法,你知道它究竟是什么吗? 目录 一、简介         1.为什么不能贪心?         2.揭秘 dp   二、应用         1.定义         2.边界值         3.动态转移方程         4.结果         5.代码

    2024年04月09日
    浏览(45)
  • 算法——动态规划(DP,Dynamic Programming)

    动态规划常用于解决优化问题。 动态规划通常以自底向上或自顶向下的方式进行求解。 自底向上的动态规划从最简单的子问题开始,逐步解决更复杂的问题,直到达到原始问题。 自顶向下的动态规划则从原始问题出发,分解成子问题,并逐步求解这些子问题。 动态规划算法

    2024年02月02日
    浏览(50)
  • 算法基础复盘笔记Day11【动态规划】—— 区间DP、计数类DP、树形DP、记忆化搜索

    ❤ 作者主页:欢迎来到我的技术博客😎 ❀ 个人介绍:大家好,本人热衷于 Java后端开发 ,欢迎来交流学习哦!( ̄▽ ̄)~* 🍊 如果文章对您有帮助,记得 关注 、 点赞 、 收藏 、 评论 ⭐️⭐️⭐️ 📣 您的支持将是我创作的动力,让我们一起加油进步吧!!!🎉🎉 1. 题目

    2024年02月01日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包