算法
2021-12-15 17:35:30 0 举报AI智能生成
算法总结
作者其他创作
大纲/内容
高级操作
位运算
分模块划分
模拟
数组
链表
堆
哈希
队列
树
线段树
排序
二分检索
滑动窗口
动态规划
图论
数学&位运算
字符串
https://www.zhihu.com/question/24964987
五大算法
贪心法
动态规划
每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。
具备的特征
1. 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理
2. 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
3. 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）
基本步骤
1. 分析最优解的性质，同时刻画其结构特征。
2. 递归的定义最优解
3. 以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值
4. 根据计算最优值时得到的信息，构造问题的最优解
经典问题
矩阵连乘
最长公共子序列(LCS)
最长递增子序列(LIS)
凸多边形最优三角剖分
背包问题
双调欧几里得旅行商问题
跟递归/分治的区别
动态规划一般是：分治 + 最优子结构
一般来说动态规划的问题，它会是让你求一个最优解或者求一个最大值，或者求一个最少方式，或者统计之类的问题
正是因为它有所谓的这种最优子结构存在，所以在中间的每一步不需要把所有的状态都保存下来，只需要存最优的状态
两个组成部分
一个就是有所谓的缓存了或者是说状态的存储数组
第二个的话就是在每一步的话都会把次优的状态给淘汰掉，只保留在这一步里面最优或者较优的一些状态来推导出最后的全局最优
关键
动态规划 和 递归或者分治 没有根本上的区别（关键看有无最优的子结构）
共性：找到重复子问题
差异性：最优子结构、中途可以淘汰次优解
状态转移方程（DP方程）
最优子结构 opt[n]=best_of(opt[n-1], opt[n-2],...)
存储中间状态：opt[i]
递推公式（美其名曰：状态转移方程或者DP方程）
举例
斐波拉契数列DP方程:opt[i]=opt[i-1]+opt[i-2]
二维路径计数DP方程：opt[i,j] = opt[i+1][j] + opt[i][j+1] (且判断a[i,j]是否空地)
动态规划的核心不是将一个大问题拆分成小问题，而是这些拆分的”小问题“会不会被重复调用。重复调用的话就可以把中间结果保存下来，从而在之后的计算中达到复用的效果。
知乎-https://www.zhihu.com/question/39948290/answer/883302989
入门动态规划第一条：不要望文生义，不要用名字反推算法！
也就是说动态规划起的不好，不容易理解，应该叫分布规划，分布存储等更好一些
也就是说动态规划起的不好，不容易理解，应该叫分布规划，分布存储等更好一些
适合用动态规划解决的问题
在许多场景中， f(n)的显式表达式是不易得到的，大多数情况下甚至无法得到，动态规划的魅力就出来了。
显式表达式
f(n) = 2n
动态规划方程式
f(n)=f(n-1) + 2
应用动态规划——关键是将动态规划拆分成三个子目标。
动态规划与其说是一个算法，不如说是一种方法论，
该方法论主要致力于将合适的问题拆分成三个子目标一一击破。
完成该三个目标，你将所向披靡。
动态规划与其说是一个算法，不如说是一种方法论，
该方法论主要致力于将合适的问题拆分成三个子目标一一击破。
完成该三个目标，你将所向披靡。
建立状态转移方程
这一步是最难的，大部分人都被卡在这里。
这一步没太多的规律可说，只需抓住一个思维：当做已经知道f(1)~f(n-1)的值，然后想办法利用它们求得f(n)
在“数腿”的例子中，状态转移方程即为 f(n)=f(n-1) + 2
缓存同时复用以往结果
也就是搞个数组之类的变量记录中间结果。
这一步不难，但是很重要。如果没有合适地处理，很有可能就是指数和线性时间复杂度的区别。
如果刚刚缓存过子结果，只需复用这个子结果，那么将只需一次加法运算即可。
按顺序从小往大算
也就是搞个for循环依次计算。
这里的“小”和“大”对应的是问题的规模，在这里也就是我们要从 f(0), f(1) , ... 到 f(n)依次顺序计算。
当问题复杂起来的时候，有可能会乱了套，所以必须记住这也是目标之一
漫画动态规划-https://www.sohu.com/a/149075950_684445?spm=smpc.content.share.1.1602945779460SCfNW2C#comment_area
三个重要概念
最优子结构
边界
状态转移方程
动态规划的核心
决定了问题的每个阶段和下一个阶段的关系
斐波那契数列
最优子结构
f(n-1)
f(n-2)
最优子结构跟最终问题的关系
f(n)=f(n-1) + f(n-2)
边界
f(1)
f(2)
状态转移方程
f(n)=f(n-1)+f(n-2)
国王，工人和金矿（10个工人5个金矿）
最优子结构
第5个金矿不用挖
4个金矿10个工人的最优选择
第5个金矿可以挖
4个金矿（10-第5个金矿用的人）个工人的最优选择
最优子结构跟最终问题的关系
第5个金矿不用挖和第5个金矿可以挖两者的最大值！
f(5,10)=Max(f(4,10), f(4,10-P[4]) + G[4])
金矿数量表示N，工人总数表示W，金矿的黄金数量是G[]，金矿的用工数量是P[]
f(n,w)表示N个金矿，W个工人的最优解
边界
当N=1，W>=P[0]
f(N, W) = G[0]
当N=1，W<P[0]
f(N, W) = 0
状态转移方程
当n<=1, w<p[0]
f(n,w)=0
当n==1，w>=p[0]
f(n,w)=g[0]
当n>1，w<p[n-1]
f(n,w)=f(n-1, w)
当n>1, w>=p[n-1]
Max(f(n,w), f(n,w-p[n-1]) + g[n-1])
根据状态转移方程计算
递归法
备忘录算法
动态规划算法
动态规划的套路-https://zhuanlan.zhihu.com/p/91582909
关键：leetcode 连续刷几十道题，会非常有帮助
套路
无非就是利用历史记录，来避免我们的重复计算。
而这些历史记录，我们得需要一些变量来保存，一般是用一维数组或者二维数组来保存。
而这些历史记录，我们得需要一些变量来保存，一般是用一维数组或者二维数组来保存。
三步走
定义数组元素的含义
这是非常非常重要的点，规定这个数组元素的含义，例如 dp[i] 是代表什么意思？
关键：想求什么，就定义它是什么
有时候数组的含义不容易找
给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数
定义 dp[i] [j]的含义：当字符串 word1 的长度为 i，字符串 word2 的长度为 j 时。
将 word1 转化为 word2 所使用的最少操作次数为 dp[i] [j]
将 word1 转化为 word2 所使用的最少操作次数为 dp[i] [j]
找出数组元素之间的关系式
当我们要计算 dp[n] 时，是可以利用 dp[n-1]，dp[n-2].....dp[1]，来推出 dp[n] 的。
也就是可以利用历史数据来推出新的元素值，所以我们要找出数组元素之间的关系式
也就是可以利用历史数据来推出新的元素值，所以我们要找出数组元素之间的关系式
找出初始值
找出边界
给边界数组进行初始化
初始值的严谨性
初始值考虑的全面一些
小技巧
90% 的字符串问题都可以用动态规划解决，同时90%是采用二维数组。
优化
优化核心：画图！画图！画图！
最多路径数
将空间复杂度 O(n * m)，优化成 O(n)
编辑距离
基本 80% 的二维矩阵 dp 都可以优化成 一维矩阵的 dp，核心就是要画图
画二维 dp 的矩阵图，然后看元素之间的值依赖，然后就可以很清晰着知道该如何优化了
分治法
将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
具备的特征
1. 该问题的规模缩小到一定的程度就可以容易地解决
第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加
2. 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质
第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用
3. 利用该问题分解出的子问题的解可以合并为该问题的解
第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征。
如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法
如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法
4. 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题
第四条特征涉及到分治法的效率，如果各子问题是不独立的，那么分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好
基本步骤
1. 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
2. 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
3. 合并：将各个子问题的解合并为原问题的解。
经典问题
二分搜索
大整数乘法
Strassen矩阵乘法
棋盘覆盖
合并排序
快速排序
线性时间选择
最接近点对问题
循环赛日程表
汉诺塔
回溯法
分支限定法
算法分类
排序算法
快速排序
合并排序
计数排序
搜索算法
回溯
递归
剪枝技巧
图论
最短路
最小生成树
动态规划
背包问题
最长子序列
计数问题
基础技巧
分治
倍增
二分
贪心
0 条评论
下一页
