CSP-J/S复赛算法 动态规划初步

文章目录

  • 前言
  • 动态规划
  • 动态规划常见形式
    • 动态规划求最值的几个例子
      • 1. **背包问题**
      • 2. **最短路径问题**
      • 3. **最小硬币找零问题**
      • 4. **最长递增子序列**
    • 总结
  • 最优子结构
    • 举个简单的例子
    • 其他例子
    • 条件
  • DP的核心就是穷举
      • 具体解释
  • 递归的算法时间复杂度
  • dp数组的迭代解法
    • 通俗易懂的解释
    • 比喻
  • 状态转移方程详解
    • 状态转移方程中的状态概念
      • 通俗易懂的解释:
      • 举个例子:
      • 状态总结:
  • DP的无后效性
    • 通俗易懂的解释
    • 举个例子
    • 特点总结
    • 例子
  • DP的本质
    • 动态规划(DP)为什么快?
    • 通俗解释
    • 动态规划的核心是什么?
    • 如何设计DP算法
      • 1. **我是谁?(设计状态)**
      • 2. **我从哪里来?(状态表示:f(x))**
      • 3. **我要到哪里去?(设计状态转移)**
      • 设计 DP 算法的一般步骤:
      • 举个例子:
  • 总结


前言


动态规划

动态规划(Dynamic Programming)其实是一个很聪明的“拆问题”的方法。我们常常会遇到一些很大的问题,比如要做很多选择,走很多步才能完成。动态规划就是把这些问题一步步拆成小问题来解决,每次解决小问题的时候,都记住这个问题的答案,以后如果再遇到这个问题,就不用重新计算了,直接用之前的答案。

动态规划常见形式

动态规划的一个常见形式就是求最值,也就是在一系列选择中找到最优解(比如最大值或最小值)。问题可以是找最短路径、最大利润、最少步骤等等。动态规划的核心思想是通过把大问题分解成小问题,然后一步步解决小问题,最终找到整个问题的最优解。

动态规划求最值的几个例子

1. 背包问题

想象你有一个背包,能装有限的重量,同时有许多物品,每个物品有不同的重量和价值。你想装入背包的物品总价值最大,但又不能超过背包的承重。动态规划可以帮助你在选择哪些物品时,找到一个最优方案,使背包内物品的总价值最高。

2. 最短路径问题

给定一张地图,其中每条路都有一定的长度,问从起点到终点的最短距离是多少。动态规划的思路是每次选择一条最短的路,并通过递推的方式一步步缩短问题规模,最终找到从起点到终点的最短路径。

3. 最小硬币找零问题

假设你有不同面值的硬币,现在需要找一定金额的零钱,问你最少需要多少个硬币。动态规划的思路是每次都考虑使用一枚硬币,然后递归地计算剩下的金额最少需要多少硬币,通过这样的递推方式,找到找零所需的最少硬币数量。

4. 最长递增子序列

给定一个数字序列,找出其中最长的递增子序列(子序列中的数字是递增的)。动态规划的思路是从头到尾扫描数组,每次都记录以当前数字为结尾的最长递增子序列长度,最终找到全局的最长递增子序列。

总结

动态规划通常用来解决那些“从多个选择中找到最优解”的问题,比如找最大值、最小值、最长路径、最短路径等。通过把问题一步步分解并保存中间结果,动态规划能让我们高效地解决这些问题。

最优子结构

最优子结构是动态规划的核心概念之一,它指的是一个问题的最优解可以通过其子问题的最优解来构造出来。换句话说,就是大问题的最优解由若干个小问题的最优解组成。

举个简单的例子

假设我们要从城市A到城市C,途中会经过城市B。我们想知道如何从A到C的最短路径。那么,如果我们知道从A到B的最短路径,再加上从B到C的最短路径,就可以得到从A到C的最短路径。这就是最优子结构的体现:从A到C的最优解可以通过两个子问题(A到B和B到C)的最优解得到。

其他例子

  1. 背包问题
    在背包问题中,假设我们已经解决了重量为W的背包的最优解(最大价值),那么如果再给定一个物品,我们可以通过比较“放这个物品”和“不放这个物品”的两种情况,来决定最终的最优解。这里,每个背包容量的最优解都依赖于容量更小的背包的最优解。

  2. 斐波那契数列
    计算斐波那契数列时,某个位置的值是前两个位置值的和, F ( n ) = F ( n − 1 ) + F ( n − 2 ) F(n) = F(n-1) + F(n-2) F(n)=F(n1)+F(n2)。每个位置的最优解(即数值)依赖于它前面两个子问题的最优解。

条件

要满足最优子结构,问题必须具有以下两个特征:

  1. 重叠子问题:大问题可以分解成重复的小问题。
  2. 子问题独立性:每个子问题的解都是独立的,不受其他子问题解的影响。

如果一个问题具备最优子结构,就可以用动态规划来高效地求解。

DP的核心就是穷举

DP的核心是穷举。这意味着在动态规划(DP)中,解决问题的关键步骤就是穷举所有可能的解法,然后通过一些技巧来优化穷举过程

具体解释

  1. 穷举存在“重叠子问题”

    • 许多问题在求解时会遇到相同的子问题多次重复出现。如果不加优化,每次都要重新计算相同的子问题,导致时间浪费。
    • 动态规划的一个优化思路就是通过“备忘录”或“DP Table”的方式记录这些已经计算过的子问题结果,避免重复计算,从而提高效率。
  2. 具备最优子结构

    • 这是动态规划的另一个核心思想。如果一个问题的最优解可以通过它的子问题的最优解来得到,那就具备了最优子结构的性质。基于这一性质,动态规划通过递推或者递归的方式一步步求解子问题,最终获得问题的最优解。
  3. 状态转移方程

    • 状态转移方程是解决动态规划问题的关键之一。它描述了如何从一个状态转移到另一个状态,并通过合适的方式找到最优解。简而言之,状态转移方程规定了如何根据前面已知的状态推导出当前状态的解。

总结:
动态规划的核心就是通过穷举所有可能的方案,并结合备忘录来优化重叠的子问题,同时依靠最优子结构状态转移方程来一步步构建最优解。

递归的算法时间复杂度

就是其子问题个数*子问题所需要的时间

dp数组的迭代解法

当我们在解决问题时,如果把已经算过的答案记下来,就可以避免重复计算,从而更快地找到答案。这个记录答案的地方叫做DP表,就像是一张我们专门用来记答案的表格。

通俗易懂的解释

  • 备忘录就像做作业时,我们把每一步的答案写在纸上。以后如果再遇到相同的问题,就可以直接看之前写下的答案,而不用再重新算一次。

  • DP表(动态规划表)就是这张专门的“纸”,我们会把每一步的答案都写在上面。这样,当我们需要计算后面的答案时,就可以根据前面写下的答案一步步推算出来,而不是每次从头开始。

  • 自底向上推算的意思是,我们从最简单的、最小的问题开始解决,逐步解决更复杂的问题,就像搭积木一样,先搭好底部,再往上叠。

这就是「递推」的思路
这也是动态规划一般都脱离了递归,而是由循环迭代完成计算的原因

比喻

想象你在解一个迷宫,每走一步都记下路径。下一次走到同样的地方,你就可以看看之前的记录,直接走对的路,不用再迷路。这就是DP表的作用,把已经走过的路(答案)记下来,后面遇到类似的问题就可以轻松解决。

状态转移方程详解

在DP中,最重要的就是状态转移方程,它就类似于递归中的递推方程
所以我们需要详细来学它

状态转移方程中的状态概念

在动态规划的状态转移方程中,状态指的是问题在某个步骤或者某个阶段下的一个“局部解”或“情况”。每个状态代表了问题在特定条件下的当前结果。

通俗易懂的解释:

假设我们在玩一个游戏,每一步都可能会遇到不同的情况,这些“情况”就是状态。根据当前状态,你会选择不同的策略,然后转移到下一步,也就是下一个状态。

举个例子:

假设你要爬楼梯,总共有5级台阶,你每次可以选择迈1步或2步。

  • 状态就是你现在站在哪一级台阶上。例如,你站在第3级台阶时,这就是一种状态。
  • 你的状态转移可能是:如果你选择迈1步,你会到达第4级台阶;如果你选择迈2步,你就会到第5级台阶。这就是从第3级台阶(当前状态)到第4级或第5级台阶(下一个状态)的转移过程。

状态总结:

  1. 状态描述了问题的当前情况或阶段(比如爬到某一级台阶上)。
  2. 在每个状态下,都会根据某种规则转移到下一个状态(比如走一步或走两步)。
  3. 最终的目标就是从初始状态逐步转移到目标状态(比如从第0级台阶到第5级台阶)。

在动态规划中,状态就是问题的每个阶段的描述。通过找到状态间的关系(状态转移方程),我们就能一步步求解问题。

DP的无后效性

DP的无后效性,简单来说,就是在动态规划中,当前状态的选择和结果只依赖于之前的状态,而不会受到更早之前的状态影响。也就是说,过去的决策一旦做出,就不会影响后续的状态转移。

通俗易懂的解释

无后效性就像是你做一道数学题,每一步的答案只需要看你前一步的结果,不需要再回头看更早的步骤。只要你知道了上一步的结果,就可以推算出下一步,不用管更前面的细节。

举个例子

假设你在走迷宫,你每一步的方向选择只取决于你现在站在哪个路口,不会因为你从哪个路口走到这里而影响接下来的选择。只要知道当前的位置,你就能决定下一步怎么走,不需要回顾整个走过的路径。

特点总结

  • 只看当前,不看过去:当前的状态转移只取决于前一个状态,而不会回头依赖更早的状态。
  • 每一步决策独立:当前状态的决策不会受到过去的具体路径影响,只要前一步的结果是正确的,就能继续往前推算。

例子

比如你在计算爬楼梯的方式:

  • 如果你站在第3级台阶上,你的下一步可以选择迈1步到第4级,或者迈2步到第5级。
  • 这时,你的选择只依赖于当前第3级台阶,而不需要回顾你之前是从第1级台阶还是第2级台阶到的第3级

无后效性是动态规划的核心之一,它保证了我们可以通过递推、一步步从前向后计算每个状态,而不用担心更早的状态对结果的影响。

DP的本质

动态规划(DP)为什么快?

动态规划之所以快,是因为它解决了重叠子问题。通过记录(缓存)已经计算过的子问题结果,避免重复计算,从而大大提高了效率。这种记录的方式叫做备忘录DP表。动态规划通过这些优化,使得原本指数级的复杂度问题可以降低到多项式级别,大大加快了求解速度。

通俗解释

假设你在爬山,每次爬到某个高度,你会把这个高度的路线记录下来。下次再到这个高度时,就不用再重新走一遍所有可能的路线,只需要直接看之前记下的路线就可以继续往前走。这样省去了重复走老路的时间和精力,整体速度就快了很多。

动态规划的核心是什么?

动态规划的核心是穷举,但它通过记忆化状态转移来减少重复计算,从而使得穷举变得可行和高效。核心概念包括:

  1. 重叠子问题:问题可以被分解成多个重复的小问题,解决一次就不需要再解决第二次。DP通过记忆(比如用表格记录)已经解决的子问题,避免重复计算。

  2. 最优子结构:当前问题的最优解可以通过子问题的最优解来构造,这意味着我们可以一步步构建出整个问题的最优解。

  3. 状态转移方程:这是描述如何从一个状态转移到另一个状态的公式,它是动态规划的核心步骤,指导如何从已知解推导出未知解。

设计动态规划(DP)算法通常可以分为几个关键步骤,每个步骤都帮助我们一步步明确如何通过状态转移来求解问题。根据你上传的图片,可以简化为几个核心问题:

如何设计DP算法

1. 我是谁?(设计状态)

  • 状态代表了问题在某一个时刻或某一局部的情况,通常用一个变量或一组变量来描述。
  • 你需要明确在这个问题的解法中,每一个状态要代表什么,例如当前已经完成了哪些任务或已经走到了哪一步。

2. 我从哪里来?(状态表示:f(x))

  • 这里是设计递推关系,定义如何从之前的状态推导出当前状态的值。
  • 也就是状态转移方程,它告诉我们如何从小规模的问题一步步推导到大规模的解。例如,在求解某个问题时,当前状态可能是由前一个状态或几个前面的状态决定的。

3. 我要到哪里去?(设计状态转移)

  • 这一步要明确最终的目标,也就是最优解的状态是什么。通常是你要求解的问题的最优答案或者目标状态,比如走到终点、获得最大收益等。

设计 DP 算法的一般步骤:

  1. 定义状态:明确问题的每一步局部的情况,用状态表示出来。
  2. 确定状态转移方程:找出如何通过子问题的解来推导出当前状态的解。
  3. 设定边界条件:初始化一些最基础的状态,也就是边界条件。
  4. 最终解:找到你要的最终目标,这个目标通常是状态中的一个解。

举个例子:

假设我们要求一个阶梯问题,问你走到第 (n) 级台阶有多少种走法,规则是每次你可以选择走 1 级或 2 级。

  • 设计状态:令 (f(n)) 表示到达第 (n) 级台阶的走法总数。
  • 状态转移方程:你可以从第 (n-1) 级台阶走一步到 (n),也可以从第 (n-2) 级台阶走两步到 (n)。因此,状态转移方程是:
    f ( n ) = f ( n − 1 ) + f ( n − 2 ) f(n) = f(n-1) + f(n-2) f(n)=f(n1)+f(n2)
  • 边界条件:第 0 级台阶(地面)只有一种走法,站在那里不动,因此 (f(0) = 1),而第 1 级台阶只有一种走法,从第 0 级走一步,(f(1) = 1)。
  • 最终解:目标是求 (f(n)),即到达第 (n) 级台阶的所有走法。

通过这些步骤,你就能把原本复杂的问题拆解成小问题,逐步递推解决。

在这里插入图片描述


总结

上一篇:用于视觉的MetaFormer基线模型


下一篇:SpringBoot开发——整合Jackson实现对敏感信息进行脱敏处理