2023年精品计划1动态规划入门到熟悉看不懂来打我啊x.docx

《2023年精品计划1动态规划入门到熟悉看不懂来打我啊x.docx》由会员分享，可在线阅读，更多相关《2023年精品计划1动态规划入门到熟悉看不懂来打我啊x.docx（16页珍藏版）》请在金锄头文库上搜索。

1、【精品计划1】动态规划入门到熟悉，看不懂来打我啊x 【精品计划 1 】动态规划入门到熟悉，看不懂来打我啊 持续更新。 2.1 斐波那契系列问题 2.2 矩阵系列问题 2.3 跳跃系列问题 3.1 01 背包 3.2 完全背包 3.3 多重背包 3.4 一些变形选讲 2.1 斐波那契系列问题 在数学上，斐波纳契数列以如下被以递归的方法定义：F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-2)（ngt;=2，nisin;N*）根据定义，前十项为 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 例 1：给定一个正整数 n，求出斐波那契数列第 n 项（这时 n 较小）

2、解法一：完全抄定义 def f(n): if n=1 or n=2: return 1 return f(n-1)+f(n-2) 分析一下，为什么说递归效率很低呢？咱们来试着运行一下就知道了： 比如想求 f(10)，计算机里怎么运行的？ 想算出 f(10)，就要先算出 F(9), 想算出 f(9)，就要先算出 F(8), 想算出 f(8)，就要先算出 F(7), 想算出 f(7)，就要先算出 F(6) 兜了一圈，我们发现，有相当多的计算都重复了，比如红框部分： 那如何解决这个问题呢？问题的原因就在于，我们算出来某个结果，并没有记录下来，导致了重复计算。那很容易想到如果我们把计算的结果全都保存下

3、来，按照一定的顺序推出 n 项，就可以提升效率 解法 2： def f1(n): if n=1 or n=2: return 1 l=0*n #保存结果 l0,l1=1,1 #赋初值 for i in range(2,n): li=li-1+li-2 #直接利用之前结果 return l-1 可以看出，时间 o(n)，空间 o(n)。 继续思考，既然只求第 n 项，而斐波那契又严格依赖前两项，那我们何必记录那么多值浪费空间呢？只记录前两项就可以了。 解法 3： def f2(n): a,b=1,1 for i in range(n-1): a,b=b,a+b return a 补充： 1. p

4、at、蓝桥杯等比赛原题：求的 n 很大，F(N)模一个数。应每个结果都对这个数取模，否则：第一，计算量巨大，浪费时间；第二，数据太大，爆内存， 2. 对于有多组输入并且所求结果类似的题，可以先求出所有结果存起来，然后直接接受每一个元素，在表中查找相应答案 3. 此题有快速幂算法，但是碍于篇幅和同学们水平有限，不再叙述，可以自行学习。 例 2：一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n级的台阶总共有多少种跳法。 依旧是找递推关系： 1）跳一阶，就一种方法 2）跳两阶，它可以一次跳两个，也可以一个一个跳，所以有两种 3）三个及三个以上，假设为 n 阶，青蛙可以是跳一

5、阶来到这里，或者跳两阶来到这里，只有这两种方法。 它跳一阶来到这里，说明它上一次跳到 n-1 阶， 同理，它也可以从 n-2 跳过来 f（n）为跳到 n 的方法数，所以，f(n)=f(n-1)+f(n-2) 优化思路与例 1 类似，请自行思考。 例 3：我们可以用 2*1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2*1的小矩形无重叠地覆盖一个 2*n 的大矩形，总共有多少种方法？ N=1: 只有一种 N=2，两种: N=3: 读到这里，你们应该能很快想到，依旧是斐波那契式递归啊。 对于 ngt;=3:怎么能覆盖到三？ 只有两种办法，从 n-1 的地方竖着放了一块，或者从 n-2

6、的位置横着放了两块 例 4：给定一个由 0-9 组成的字符串，1 可以转化成 A，2 可以转化成 B。依此类推。25 可以转化成 Y，26 可以转化成 z，给一个字符串，返回能转化的字母串的有几种？ 比如：123，可以转化成 1 、2 、3 变成 ABC， 12 、3 变成 LC， 1 、23 变成 AW 三种，返回三， 比如 99999，就一种：iiiii，返回一。 分析：求 i 位置及之前字符能转化多少种。 两种转化方法 1）字符 i 自己转换成自己对应的字母 2）和前面那个数组成两位数，然后转换成对应的字母 假设遍历到 i 位置，判断 i-1 位置和 i 位置组成的两位数是否大于 26，

7、大于就没有第二种方法，f(i)=f(i-1),如果小于 26， f(i)=f(i-1)+f(i-2) 2.2 矩阵系列问题 例 5：给一个由数字组成的矩阵，初始在左上角，要求每次只能向下或向右移动，路径和就是经过的数字全部加起来，求可能的最小路径和。 1 3 5 9 8 1 3 4 5 0 6 1 8 8 4 0 路径：1 3 1 0 6 1 0 路径和最小，返回 12 分析：我们可以像之前一样，暴力的把每一种情况都试一次，但是依旧会造成过多的重复计算，以本题为例子最后解释一下暴力慢在哪里，以后不再叙述了。 比如本题来讲，我们尝试如下路径： 有很多路是重复走过的一遍。 再进一步说： 从 1 到

8、 6 位置，有很多路可以走，直观感受一下： 所有路中，一定会有和最小的，但是我们并不知道，每次尝试一次 1-gt;6-gt;终点的路线时，我们把所有的情况都算了一遍，这过程中我们浪费了相当多的有效信息。 这就是暴力的结果。 优化做法：生成和矩阵相同大小的二维表，用来记录到起点每个位置的最小路径和 接下来带着大家真正进入动态规划； 第一步：初始化（对于本题来说，第一列和第一行，我们别无选择，就一条路，因此，我们可以直接确定答案） 第二步：确定其余位置如何推出（我们称为状态转移方程） 直观来说，每个位置只可能是从上面，或者左边走来的： 对于普遍的位置 i，j，只有 i-1,j 和 i,j-1 这两

9、个位置可以一步走到这里，所以 DPi,j=min(DPi,j-1,DPi-1,j）+Li,j（之前的最优解加上本位置的数字） 继续优化：和之前一样，这个式子实际上也是严格依赖两个值，一个是左边的值，一个是上面的值，所以，我们按之前的思路，应该可以想到可以压缩空间。 我们尝试用一维的空间来解题： 想象这是我们的第一行答案： 我们如何利用仅有的一维空间来更新出下一行呢？ 我们要想： bull; 我们需要左面的数字，所以，本位置的左边必须是更新过的数字（否则就是左上的位置了），所以应该从左往右。 bull; 我们需要上面的数字，这个不需要更新，本来就需要本位置的旧数字。 本题第二行为：8，1，3，4

10、 第一行答案为 依次更新： 更新 A： （只能向下走） 更新 B： （比较从左边来和从上面来哪里比较小） 更新 C： 更新 D： 最后我们可以发现，伪代码是这样的： For i 0 -gt; 高度: For j 0 -gt; 宽度 DPj=min(DPj-1,DPj）+Li,j 时间不变，空间优化到 o(min（高，宽） 例 6：给一个由数字组成的矩阵，初始在左上角，要求每次只能向下或向右移动，路径和就是经过的数字全部加起来，求可能的最大路径和。 和例 5 只差一个大字，请自己思考 例 7：一个矩阵，初始在左上角，要求每次只能向下或向右移动，求到终点的方法数。 和例 5，6 类似，只是方法数应

11、该等于，左边的方法数加上上面的方法数 第二章末练习 1 一个只包含A、B和C的字符串，如果存在某一段长度为 3 的连续子串中恰好A、B和C各有一个，那么这个字符串就是纯净的，否则这个字符串就是暗黑的。例如： BAACAACCBAAA 连续子串CBA中包含了A,B,C各一个，所以是纯净的字符串 AABBCCAABB 不存在一个长度为 3 的连续子串包含A,B,C,所以是暗黑的字符串 你的任务就是计算出长度为 n 的字符串(只包含A、B和C)，有多少个是暗黑的字符串。(网易 17 校招原题) 2、X 国的一段古城墙的顶端可以看成 2*N 个格子组成的矩形（如下图所示），现需要把这些格子刷上保护漆。

12、 你可以从任意一个格子刷起，刷完一格，可以移动到和它相邻的格子（对角相邻也算数），但不能移动到较远的格子（因为油漆未干不能踩！） 比如：a d b c e f 就是合格的刷漆顺序。 c e f d a b 是另一种合适的方案。 当已知 N 时，求总的方案数。当 N 较大时，结果会迅速增大，请把结果对 1000000007 (十亿零七) 取模。 3.1 01 背包 入门了动态规划之后，我们来看一个经典系列问题：背包问题 这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。 用子问题定义状态： fij表示前 i 件物品恰放入一个容量为 j 的背包可以获得的最大价值。则其状态转移方程为

13、： 将前 i 件物品放入容量为 j 的背包中这个子问题，若只考虑第 i 件物品的策略（放或不放），那么就可以转化为一个只牵扯前 iminus;1 件物品的问题。 如果不放第 i 件物品，那么问题就转化为前 iminus;1 件物品放入容量为 j 的背包中，价值为 fiminus;1j； 如果放第 i 件物品，那么问题就转化为前 iminus;1 件物品放入剩下的容量为 jminus;ci的背包中，此时能获得的最大价值就是 fiminus;1jminus;wi,再加上通过放入第 i 件物品获得的价值 vi。 因此得出上面的式子。 继续优化空间（利用之前提到的知识）： 如果我们压缩到一维空间解题，

14、这次我们需要的是上面的位置和左上的位置，也就是说，我们需要左边的位置是没被更新过的，得出更新顺序应该从右往左： for i in range(1,n+1): for j in range(v,-1,-1) fj = max(fj, fj - wi + vi); 3.2 完全背包 这个问题非常类似于 01 背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取 0 件、取 1 件、取 2 件等很多种。如果仍然按照解 01 背包时的思路,很容易得出： 这跟 01 背包问题一样有 O(VN)个状态需要求解，但求解每个状态的时间已经不是常数了 而是 ，总的复杂度可以认为是 ,将 0