网站面向哪些地区做优化容易,微网站是什么,做设计应该看哪些网站,工作手机持续更新。。。。。。
2.1斐波那契系列问题
2.2矩阵系列问题
2.3跳跃系列问题
3.1 01背包
3.2 完全背包
3.3多重背包
3.4 一些变形选讲 2.1斐波那契系列问题
在数学上#xff0c;斐波纳契数列以如下被以递归的方法定义#xff1a;F(0)0#xff0c;F(1)1, F(n)F(n-1)…持续更新。。。。。。
2.1斐波那契系列问题
2.2矩阵系列问题
2.3跳跃系列问题
3.1 01背包
3.2 完全背包
3.3多重背包
3.4 一些变形选讲 2.1斐波那契系列问题
在数学上斐波纳契数列以如下被以递归的方法定义F(0)0F(1)1, F(n)F(n-1)F(n-2)n2n∈N*根据定义前十项为1, 1, 2, 3, 5, 8, 13, 21, 34, 55 例1给定一个正整数n求出斐波那契数列第n项这时n较小
解法一完全抄定义
def f(n):if n1 or n2:return 1return f(n-1)f(n-2) 分析一下为什么说递归效率很低呢咱们来试着运行一下就知道了 比如想求f(10)计算机里怎么运行的 想算出f(10)就要先算出F(9),
想算出f(9)就要先算出F(8),
想算出f(8)就要先算出F(7),
想算出f(7)就要先算出F(6)……
兜了一圈我们发现有相当多的计算都重复了比如红框部分 那如何解决这个问题呢问题的原因就在于我们算出来某个结果并没有记录下来导致了重复计算。那很容易想到如果我们把计算的结果全都保存下来按照一定的顺序推出n项就可以提升效率 解法2
def f1(n):if n1 or n2:return 1l[0]*n #保存结果l[0],l[1]1,1 #赋初值for i in range(2,n):l[i]l[i-1]l[i-2] #直接利用之前结果return l[-1]
可以看出时间o(n)空间o(n)。
继续思考既然只求第n项而斐波那契又严格依赖前两项那我们何必记录那么多值浪费空间呢只记录前两项就可以了。 解法3
def f2(n):a,b1,1for i in range(n-1):a,bb,abreturn a
补充
pat、蓝桥杯等比赛原题求的n很大F(N)模一个数。应每个结果都对这个数取模否则第一计算量巨大浪费时间第二数据太大爆内存对于有多组输入并且所求结果类似的题可以先求出所有结果存起来然后直接接受每一个元素在表中查找相应答案此题有快速幂算法但是碍于篇幅和同学们水平有限不再叙述可以自行学习。例2一只青蛙一次可以跳上1级台阶也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 依旧是找递推关系
1跳一阶就一种方法
2跳两阶它可以一次跳两个也可以一个一个跳所以有两种
3三个及三个以上假设为n阶青蛙可以是跳一阶来到这里或者跳两阶来到这里只有这两种方法。
它跳一阶来到这里说明它上一次跳到n-1阶
同理它也可以从n-2跳过来 fn为跳到n的方法数所以f(n)f(n-1)f(n-2) 优化思路与例1类似请自行思考。 例3我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形总共有多少种方法 N1: 只有一种
N2两种: N3: 读到这里你们应该能很快想到依旧是斐波那契式递归啊。 对于n3:怎么能覆盖到三
只有两种办法从n-1的地方竖着放了一块或者从n-2的位置横着放了两块 例4给定一个由0-9组成的字符串1可以转化成A2可以转化成B。依此类推。。25可以转化成Y26可以转化成z给一个字符串返回能转化的字母串的有几种 比如123可以转化成
1 、2 、3变成ABC
12 、3变成LC 1 、23变成AW
三种返回三 比如99999就一种iiiii返回一。 分析求i位置及之前字符能转化多少种。 两种转化方法
1字符i自己转换成自己对应的字母
2和前面那个数组成两位数然后转换成对应的字母 假设遍历到i位置判断i-1位置和i位置组成的两位数是否大于26大于就没有第二种方法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到6位置有很多路可以走直观感受一下 所有路中一定会有和最小的但是我们并不知道每次尝试一次1-6-终点的路线时我们把所有的情况都算了一遍这过程中我们浪费了相当多的有效信息。 这就是暴力的结果。 优化做法生成和矩阵相同大小的二维表用来记录到起点每个位置的最小路径和 接下来带着大家真正进入动态规划
第一步初始化对于本题来说第一列和第一行我们别无选择就一条路因此我们可以直接确定答案 第二步确定其余位置如何推出我们称为状态转移方程
直观来说每个位置只可能是从上面或者左边走来的 对于普遍的位置ij只有i-1,j和i,j-1这两个位置可以一步走到这里所以
DP[i,j]min(DP[i,j-1],DP[i-1,j]L[i,j]之前的最优解加上本位置的数字 继续优化和之前一样这个式子实际上也是严格依赖两个值一个是左边的值一个是上面的值所以我们按之前的思路应该可以想到可以压缩空间。
我们尝试用一维的空间来解题
想象这是我们的第一行答案 我们如何利用仅有的一维空间来更新出下一行呢
我们要想
我们需要左面的数字所以本位置的左边必须是更新过的数字否则就是左上的位置了所以应该从左往右更新。我们需要上面的数字这个不需要更新本来就需要本位置的旧数字。
本题第二行为8134
第一行答案为 依次更新 更新A 只能向下走
更新B 比较从左边来和从上面来哪里比较小
更新C 更新D 最后我们可以发现伪代码是这样的
For i 0 - 高度: For j 0 - 宽度
DP[j]min(DP[j-1],DP[j]L[i,j] 时间不变空间优化到o(min高宽 例6给一个由数字组成的矩阵初始在左上角要求每次只能向下或向右移动路径和就是经过的数字全部加起来求可能的最大路径和。 和例5只差一个“大”字请自己思考 例7一个矩阵初始在左上角要求每次只能向下或向右移动求到终点的方法数。 和例56类似只是方法数应该等于左边的方法数加上上面的方法数 第二章末练习
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个格子组成的矩形如下图所示现需要把这些格子刷上保护漆。 你可以从任意一个格子刷起刷完一格可以移动到和它相邻的格子对角相邻也算数但不能移动到较远的格子因为油漆未干不能踩
比如a d b c e f 就是合格的刷漆顺序。
c e f d a b 是另一种合适的方案。
当已知 N 时求总的方案数。当N较大时结果会迅速增大请把结果对 1000000007 (十亿零七) 取模。
3.1 01背包
入门了动态规划之后我们来看一个经典系列问题背包问题 这是最基础的背包问题特点是每种物品仅有一件可以选择放或不放。
用子问题定义状态
f[i][j]表示前i件物品恰放入一个容量为j的背包可以获得的最大价值。则其状态转移方程为 “将前i件物品放入容量为j的背包中”这个子问题若只考虑第i件物品的策略放或不放那么就可以转化为一个只牵扯前i−1件物品的问题。
如果不放第i件物品那么问题就转化为“前i−1件物品放入容量为j的背包中”价值为f[i−1][j]
如果放第i件物品那么问题就转化为“前i−1件物品放入剩下的容量为j−c[i]的背包中”此时能获得的最大价值就是f[i−1][j−w[i]],再加上通过放入第i件物品获得的价值v[i]。
因此得出上面的式子。
继续优化空间利用之前提到的知识
如果我们压缩到一维空间解题这次我们需要的是上面的位置和左上的位置也就是说我们需要左边的位置是没被更新过的得出更新顺序应该从右往左
for i in range(1,n1):
for j in range(v,-1,-1) f[j] max(f[j], f[j - w[i]] v[i]);
3.2 完全背包 这个问题非常类似于01背包问题所不同的是每种物品有无限件。也就是从每种物品的角度考虑与它相关的策略已并非取或不取两种而是有取0件、取1件、取2件……等很多种。如果仍然按照解01背包时的思路,很容易得出 这跟01背包问题一样有O(VN)个状态需要求解但求解每个状态的时间已经不是常数了
而是总的复杂度可以认为是,将01背包问题的基本思路加以改进得到了这样一个清晰的方法。这说明01背包问题的方程的确是很重要可以推及其它类型的背包问题。但我们还是试图改进这个复杂度。
我们可以知道对于一个普遍位置w当前物品代价为2的话下图中红色区域就是和位置w的取值相关的一些数值 对当前物品的决策就依次是不拿、拿一个、拿两个、拿三个对应上面式子中的k
我们算法优化的思路就是不断去除重复计算显然我们可以继续优化这个式子。
请思考我们的E3位置是如何得出的其实是根据三个红色区域得出的但是我们算位置w时又算了一遍显然是重复了。而E3其实包含了不拿、拿一个、拿两个这些情况中的最优解我们算w时直接用就可以了。 给出模板代码
for (int i 1; i n; i) for (int j w[i]; j V; j) f[j] max(f[j], f[j - w[i]] v[i]); 对比两种背包
这个代码与01背包的代码只有j的循环次序不同而已。为什么这样一改就可行呢
首先想想为什么01背包中要按照jV...0 jV...0jV...0的逆序来循环。这是因为要保证第i次循环中的状态f[i][j]是由状态f[i−1][j−w[i]]递推而来。换句话说这正是为了保证每件物品只选一次保证在考虑“选入第i件物品”这件策略时依据的是一个绝无已经选入第i件物品的子结果f[i−1][j−w[i]]。
而现在完全背包的特点恰是每种物品可选无限件所以在考虑“加选一件第i ii种物品”这种策略时却正需要一个可能已选入第i种物品的子结果f[i][j−w[i]]所以就可以并且必须采用j0...V j0...Vj0...V的顺序循环。这就是这个简单的程序为何成立的道理。
最终给出状态转移方程给不明白的同学看 也可以通过数学导出此式 3.3多重背包 和之前的背包不同每种物品不是只有一件也不是有无限件这次的每种物品的数量都是有限制的我们对于每种物品可以选择拿一件、两件……p[i]件。
我们借用上一种问题的图 看起来是类似的位置w依旧和红色区域相关但是我们可以直接根据E3来求出位置w吗是不能的因为条件变了每种物品不是无限的可能在w位置图中椭圆圈出的位置代表着需要拿三个但是如果规定最多拿两个我们这种算法就出问题了。 一种做题思路把每个物品都按01背包做比如第i种物品我们就按有p[i]件相同的物品。每一种物品都是如此按01背包做就可以了。但是显然很蠢 改进
我们平时买东西时难道带的全是一元的硬币吗当然不是只要手中的钱可以凑出商品的价格即可比如9元的东西我不一定用九个硬币背包问题的物品来付钱可以5元4个1元。
背包问题也一样我们不一定要全部拆成1的物品只要我们的物品可以代表0——p[i]的所有情况我们就认为这种策略是正确的。
那如何拆p[i]个物品可以保证我们的物品可以代表0——p[i]的所有情况呢这里要借助2进制思想。
一个n位的二进制数可以取0到2的n次方-1第i位代表的是2的i-1次方。
对应到物品
我们的p[i]15我们怎样拆呢
1248即可这四个数一定可以组合出0-15的任何一个数。 二进制拆分代码如下 for (int i 1; i n; i) { int num min(p[i], V / w[i]); for (int k 1; num 0; k 1) { if (k num) k num; num - k; for (int j V; j w[i] * k; j--) f[j] max(f[j], f[j - w[i] * k] v[i] * k); }
}
3.4 一些变形选讲
1最常见的一些变形甚至不能说是变形上面也提到过但是怕同学们不知道
我们常见的问题中一般是问最优解可能是最大或者最小但是问题也可能是方法的数量这个时候一般把状态转移方程中的max(min)改为sum求和即可当然压缩空间后的样子还是需要自己写。
2初始化的细节问题
我们看到的求最优解的背包问题题目中事实上有两种不太相同的问法。有的题目要求恰好装满背包时的最优解有的题目则并没有要求必须把背包装满。这两种问法的区别是在初始化的时候有所不同。
如果是第一种问法要求恰好装满背包那么在初始化时除了f[0]为0其它f[1...V]均设为−∞这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。
如果并没有要求必须把背包装满而是只希望价格尽量大初始化时应该将f[0...V]全部设为0。
为什么呢可以这样理解初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满那么此时只有容量为0的背包可能被价值为0的nothing “恰好装满”其它容量的背包均没有合法的解属于未定义的状态它们的值就都应该是
−∞了。如果背包并非必须被装满那么任何容量的背包都有一个合法解“什么都不装”这个解的价值为0所以初始时状态的值也就全部为0了。
3常数优化
前面的代码中有for(jV...w[i])还可以将这个循环的下限进行改进。
由于只需要最后f[j]的值倒推前一个物品其实只要知道f[j−w[n]]即可。以此类推对以第j个背包其实只需要知道到f[j−sumw[j...n]]即可代码自行修改。
4其实拆解二进制物品并不是多重背包的最优解但是最优的单调队列思想写起来有些繁琐可能以后会写。 可以刷的题
鉴于有一些同学说简单我把去年写的一些题解放在这里
背包是否装满
单调栈
单调双端队列
双端队列优化的背包问题
字符串上的动态规划
皇后问题位运算
旅行商问题认识状态压缩
蓝桥杯 摔手机 费时巨多的题解
2018hbcpc dp总结
HDU1029 HDU1087 HDU1176 HDU1257 POJ1458
POJ2533 HDU1114 HDU1260 HDU1160
HDU1069 POJ3616 POJ1088
POJ1189 UVA12511 HDU2845 HBCPC2018 K
leetcode516 最长回文子序列
leetcode104 二叉树的最大深度
leetcode403 青蛙过河
leetcode115 不同的子序列
leetcode32 最长有效括号
leetcode 152 乘积最大子序列
leetcode221 最大正方形
leetcode213 打家劫舍II
leetcode97 交错字符串
leetcode542 01矩阵
leetcode303 区域和检索
leetcode72 编辑距离
leetcode45 跳跃游戏II 秒杀所有答案
leetcode55 跳跃游戏 秒杀所有答案
leetcode63 不同路径II
leecode5 最长回文子串
leetcode300 最长上升子序列
leetcode64 最小路径和
leecode53 最大子序列和
leecode11 盛水最多的容器
leetcode538 把二叉搜索树转换成累加树
leetcode322 零钱兑换
leetcode70 爬楼梯
leetcode121买卖股票的最佳时机
