算法套路与框架
动态规划
动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法,只不过在计算机问题上应用比较多,比如说让你求最长递增子序列呀,最小编辑距离呀等等。
核心问题是穷举。因为要求最值,肯定要把所有可行的答案穷举出来,然后在其中找最值。
- 首先,动态规划这类问题存在「重叠子问题」,如果暴力穷举的话效率会极其低下,所以需要「备忘录」或者「DP table」来优化穷举过程,避免不必要的计算
- 一定会具备「最优子结构」,才能通过子问题的最值得到原问题的最值
另外,虽然动态规划的核心思想就是穷举求最值,但是问题可以千变万化,穷举所有可行解其实并不是一件容易的事,只有列出正确的「状态转移方程」才能正确地穷举。但是在实际的算法问题中,写出状态转移方程是最困难的,这里提供一个思维框架,辅助思考状态转移方程:
明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义
1 | # 初始化 base case |
回溯算法
解决一个回溯问题,实际上就是一个决策树的遍历过程。你只需要思考 3 个问题:
1、路径:也就是已经做出的选择。
2、选择列表:也就是你当前可以做的选择。
3、结束条件:也就是到达决策树底层,无法再做选择的条件。
回溯算法的框架:
1 | result = [] |
其核心就是 for 循环里面的递归,在递归调用之前「做选择」,在递归调用之后「撤销选择」,特别简单。
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 spaceman!