请人做软件开发的网站,h5移动网站开发,wordpress个人模板,阿里云如何建立网站截图摘自湖南大学彭鹏老师的ppt。笔记也是根据他的ppt整理的。
动态规划
核心
用数组记录中间结果#xff0c;避免重复计算
三角数塔问题
问题描述
给定一个三角形数塔#xff0c;从顶部出发#xff0c;每次只能移动到下一行的相邻元素。要求找到一条路径#xff0c;…截图摘自湖南大学彭鹏老师的ppt。笔记也是根据他的ppt整理的。
动态规划
核心
用数组记录中间结果避免重复计算
三角数塔问题
问题描述
给定一个三角形数塔从顶部出发每次只能移动到下一行的相邻元素。要求找到一条路径使得路径上的数字和最大。
假设有一个三角形数塔如下所示 37 42 4 68 5 9 3dp数组 dp[i][j]表示以matrix[i][j]为结尾的最大路径的和 310 712 14 1320 19 23 16最后结果是23
解题思路
dp[i][j]max(dp[i-1][j],dp[i-1][j1])matrix[i][j];
伪代码 int max_value(vectorvectorint matrix ){vectorvectorint dp(matrix.size(),vectorint(matrix.size()));dp[0][0] matrix[0][0];for(int i1;imatrix.size();i){dp[i][0] dp[i-1][0] matrix[i][0]; // 最左边的for(int j1;ji;j){// 中间的dp[i][j] max(dp[i-1][j-1],dp[i-1][j]) matrix[i][j];}// 最右边的dp[i][i] dp[i-1][i-1] matrix[i][i];}return max(dp.back().begin(),dp.back().end());
};
复杂度分析
时间复杂度O(n^2)其中 n 是三角形的行数。 空间复杂度O(n^2)其中 n 是三角形的行数。
最大字段和
问题描述
给定由n个整数可能有负整数组成的序列(a1, a2, …, an)最大子段和问题要求该序列形如 的最大值1≤i≤j≤n当序列中所有整数均为负整数时其最大子段和为0。
示例
例如序列(-20,11,-4,13, -5, -2)的最大子段和为 a2a3a420 。
dp[i]表示以a[i]开头的从a[i]–a.back()的最大子段和
dp数组
dp[i] max(dp[i1]a[i],a[i]);
123456a-2011-413-5-2dp020913-5-2
所以最后答案是20
// 注意是后序
int max_sub_array(vectorint a){int n a.size();vectorint dp(n);dp.back() a.back();int max_sum a[0];for(int in-2;i0;i--){dp[i] max(dp[i1]a[i],a[i]);max_sum max(max_sum,dp[i]);}return max_sum;
}复杂度分析
时间复杂度O(n)其中 n 是序列的长度。 空间复杂度O(n)其中 n 是序列的长度。
最长公共子序列
问题描述
给定两个字符串str1和str2返回两个字符串的最长公共子序列LCS。
子序列是指从原字符串中删除若干个字符后不改变剩余字符顺序得到的字符串。最长公共子序列是两个字符串所共同拥有的最长子序列。
例如对于字符串abcde和ace最长公共子序列是ace因此长度为3。
示例
abcbdab bdcaba
dp[i][j]表示str1[0:i]和str2[0:j]的最长公共子序列长度
startabcbdabstart00000000b00111111d00111222c00122222a01122233b01223334a01223344
所以最后答案是4 bdab
代码
int longest_common_subsequence(string str1,string str2){int n str1.size();int m str2.size();vectorvectorint dp(n1,vectorint(m1,0));for(int i1;in;i){for(int j1;jm;j){if(str1[i-1] str2[j-1]){dp[i][j] dp[i-1][j-1]1;}else{dp[i][j] max(dp[i-1][j],dp[i][j-1]);}}}return dp[n][m];
}复杂度分析
时间复杂度O(nm)其中 n 和 m 分别是字符串 str1 和 str2 的长度。 空间复杂度O(nm)其中 n 和 m 分别是字符串 str1 和 str2 的长度。
01背包问题
问题描述
给定 n 种物品和一个容量为 w 的背包每种物品都只有一件可用。第 i 种物品的体积是 vi价值是 wi。求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。输出最大价值。
示例
number4 capacity8
i1234s (weight)2345v (value)3456
dp数组
dp[i][j]表示在总容量为j的情况下在0~i个物品中能获得的最大价值。
dp[i][j]max(dp[i-1][j],dp[i-1][j-s[i]]v[i])
01234567810033333332003447777300344789940034478910
代码
int max_value_in_knapsack(vectorint s,vectorint v,int capacity){int n s.size();vectorvectorint dp(n1,vectorint(capacity1,0));for(int i1;in;i){for(int j1;jcapacity;j){if(js[i-1]){dp[i][j] max(dp[i-1][j],dp[i-1][j-s[i-1]]v[i-1]);}else{dp[i][j] dp[i-1][j];}}}return dp[n][capacity];
}复杂度分析
时间复杂度O(nm)其中 n 和 m 分别是物品的数量和背包容积。 空间复杂度O(nm)其中 n 和 m 分别是物品的数量和背包容积。
贪心算法
选取局部最优解
优缺点
优点速度快复杂度低缺点需要证明是最优解
活动选择问题
问题描述
假设我们存在这样一个活动集合S{a1,a2,a3,a4,…,an},其中每一个活动ai都有一个开始时间si和结束时间fi保证(0≤sifi),活动ai进行时那么它占用的时间为[si,fi)现在这些活动占用一个共同的资源(教室)就是这些活动会在某一时间段里面进行安排如果两个活动ai和aj的占用时间[si,fi),[sj,fj)不重叠那么就说明这两个活动是兼容的也就是说当sjfi或者sifj那么活动ai,aj是兼容的。在活动选择问题中我们希望选出一个最大兼容活动集即在同一间教室能安排数量最多的活动。
贪心策略
按照结束时间前的放前面结束时间一样的开始时间小的放前面然后依次相加
贪心证明
贪心的结果集是S, 剩下的集合是T对于T中的任意一个元素b都存在一个a属于S, 是a的结束时间大于b的开始时间。 代码
static bool cmp (const vectorinta, const vectorintb){return a[1]b[1];}
int eraseOverlapIntervals(vectorvectorint vct) {sort(vct.begin(),vct.end(),cmp);int endtimevct.front()[1];int res1;for(int i1;ivct.size();i){if(endtime vct[i][0]){}else{endtimevct[i][1];res;}}return res;}建议
碰到这种问题用动态规划也能做而且如果对应的活动有权值动态规划还一定是正确的。
对任务按照结束时间排序dp[i][j] i表示从0~i个任务j表示空余时间dp[i][j]表示最大解
哈夫曼编码
问题描述
给定一个由n个不同字符组成的字符串请设计一个哈夫曼编码使得使用该编码的编码长度最小。
哈夫曼树
定义给定n个权值作为n个叶子结点的权值构造一棵二叉树若该树的带权路径长度达到最小称这样的二叉树为最优二叉树也称为哈夫曼树(Huffman Tree)。
解法
统计待编码字符串中每个字符出现的次数并将这些次数作为权重存储在数组中。根据权重构建哈夫曼树。在构建过程中每次从权重数组中取出两个最小的权重将它们合并为一个新节点新节点的权重为这两个节点权重之和。然后将新节点加入哈夫曼树同时从权重数组中删除这两个节点。重复这个过程直到权重数组为空。根据哈夫曼树生成哈夫曼编码。对于哈夫曼树的每个叶子节点从根节点到叶子节点的路径上的每个节点对应一个0或1将这些0和1按照从根节点到叶子节点的顺序连接起来就得到了该叶子节点的哈夫曼编码。使用哈夫曼编码对字符串进行编码。将字符串中的每个字符替换为其哈夫曼编码然后将编码后的字符串按照哈夫曼编码的规则进行传输或存储。
最小延迟调度问题
问题描述
任务集合S∀i∈Sdi 为截止时间ti为加工时间di , ti为正整数。一个调度f : S→Nf(i)为任务i 的开始时间。求最大延迟达到最小的调度就是所有任务超过截止时间的和最小。 解决方案
按照结束时间di从小到大排序安排时不留空余时间
贪心证明
最优解中可以不存在相邻的逆序任务使得i,j: f(i) f(j) di dj。 真确解中交换两个任意的任务都会使得总任务拖延时间变长。
找零问题
问题描述
考虑用最少的硬币找n美分零钱的问题。假设每种硬币的面额都是整数。设计贪心算法求解找零问题假定有25美分、10美分、5美分和1美分4种面额的硬币。证明你的算法能找到最优解。
解决方案
按照先尽可能用25美分然后尽可能用10美分再尽可能用5美分最后尽可能用1美分。
贪心证明
假设一个可能的解中存在两个10一个5则可以用25代替获取到一个更优解。同样递归直到没有硬币组合能到25对应着先用25美分的。
图基本算法
广度优先搜索
算法步骤
广度优先搜索BFS,Breadth First Search从初始点开始逐层向前搜索即第n层搜索未完成不得进入下一层搜索。
深度优先搜索
算法步骤
深度优先搜索DFS,Depth First Search从初始点开始对每一个可能的分支路径深入到不能再深入为止而且每个节点只能访问一次
欧拉回路
判定条件
对于图上的任意节点入度等于出度。
DFS解法
从任意一个起始点v开始DFS遍历直到再次到达点v即寻找一个回路。将此回路定义为C如果回路C中存在某个点x其有出边不在回路中则继续以此点x开始遍历寻找回路C’将环C、C’连接起来也是一个大回路如此往复直到图G中所有的边均已经添加到回路中显然每条边只会返回一次所以复杂度为O(E)
用人话说就是
对任意一个节点A做DFS, 直到终点到了A对遍历的边进行标记把所有遍历的边去除。对任意一个还有边的点B进行DFS重复操作直到所有边都被标记。标记的边就是欧拉回路。
拓扑排序
算法步骤
找到所有入度为0的节点并加入队列依次从队列中取出节点并将其指向的节点的入度减1如果减1后该节点的入度为0则将其加入队列
最小生成树
把所有点都连接起来使得生成树各边权值之和最小。
prim算法
算法步骤
选择一个节点作为起始点并将其加入生成树中。选择与生成树相连的最小的边将其加入生成树中。重复步骤2直到所有节点都被加入生成树中。
复杂度
使用邻接矩阵表示图 O(V^2) V是顶点数量每次都要找最小的顶点使用邻接表表示图 O(ElogV) E是边的数量每次都要找最小的顶点 加入新节点的时候把新节点所有相邻的不在生成树中的边添加进去
Kruskal算法
算法步骤
按照边的权值从小到大排序依次选择边如果选择后不会形成环则加入生成树中使用并查集判断新加入的边是否会形成环
瓶颈生成树
定义
一个无向图G上的瓶颈生成树是G上一种特殊的生成树。一个瓶颈生成树T上权重最大边的权重是G中所有生成树中最小的。T上最大权重的边的权重称为T的值。 就是生成树T的最大权值是G中所有生成树中最大权值的最小值。
单源最短路径
松弛算法 说人话就是对于点u -- v , 如果找到另外一个点x使得u -- x -- v的路径更短则更新u -- v的路径。后面的Dijkstra算法Bellman-Ford算法是基于这个算法的。
Dijkstra算法
算法步骤 创建一个距离列表其中包含每个节点到起始节点的距离。起始节点的距离设置为0其他节点的距离设置为无穷大。 创建一个已访问列表和一个待访问列表。起始节点被标记为已访问其他所有节点都被标记为待访问。 对于每一个待访问的节点计算它到起始节点的距离。如果这个距离比当前记录的距离还要短那么就更新这个节点的距离。 从待访问列表中找到距离最小的节点将其标记为已访问并将其从待访问列表中移除。 重复步骤3和4直到所有的节点都被访问过。 距离列表中记录的就是每个节点到起始节点的最短距离。
缺点
无法解决边值为负值
Bellman-Ford算法
算法步骤
为每个顶点 ’ v 初始化距离数组 dist[]为dist[v] INFINITY。假设任何顶点假设为“0”作为源并分配dist 0。根据以下条件放松所有edgesuvweightN-1次 dist[v] 最小值(dist[v]dist[u] weight) 现在再次放松所有边即第N次并基于以下两种情况我们可以检测负循环 情况 1存在负循环对于任何边uv权重如果 dist[u] weight dist[v]情况 2无负循环情况 1 对于所有边均失败。
证明
N-1次可以求出最小路径
Bellman-ford算法思想是进行一次遍历遍历所有边一次一定能找到一个距离start节点最近的点N-1次之后target节点最多和start节点之间有N-2个节点
N次距离减少出现负循环回路
负权重的边又被遍历了一次
主定理
将规模为n的问题转化为a个规模为n/b的问题花费的时间是O( n d n^d nd) T(n) a ∗ T ( n b ) n d a*T(\frac{n}{b})n^d a∗T(bn)nd, 其中a1 , b1 , d0
当 a b d b^d bd , T(n)O( n d n^d nd)当 a b d b^d bd , T(n)O( n l o g b a ∗ l g n n^{log_{b} a}*lgn nlogba∗lgn)当 a b^d , T(n)O( n l o g b a n^{log_{b} a} nlogba)
不想推导直接记住吧
例子
二分查找
T(n) 2 T ( n 2 ) 1 2T(\frac{n}{2})1 2T(2n)1a2 b2 d0 -- O(n)
归并排序合并
T(n) 2 T ( n 2 ) n 2T(\frac{n}{2})n 2T(2n)na2 b2 d1 -- O(n*lgn)
递归式子
T(n) 3 T ( n 4 ) n l g n 3T(\frac{n}{4})nlg{n} 3T(4n)nlgna3 b4 d约为1.5 -- O(n*lgn)
红黑树
定义
每个节点要么是黑色要么是红色根和叶子都是黑色的所有的叶子都是NIL红色节点的父节点是黑色的从节点x到其所有后代叶子节点的所有路径中包含相同数量 的黑节点。
