算法题常见解题套路总结

很多事情做多了都能总结出一些通用的规律，算法题就有一些套路在里面，特定类型的题目有特定的解法和思路。

先大概总结一下：

• 直接暴力，如果是没见过的类型，也不涉及复杂度等外的限制，先尝试暴力法解决
• 从简单情况开始寻找规律
• 动态规划，动态规划就是寻找最优子结构，并最大化减少递归计算中重复计算子问题的情况。用动态规划时，若一时没有思路，可以先暴力，然后寻找分析暴力中哪些子问题被重复计算了，对于发现的重复计算的问题，用动态规划的方式去消除它。
• 贪心算法，若一个题具有明显的贪心倾向，可以先用贪心算法试一下
• 递归，递归在某些问题上会是问题思路更加清晰，也会大大减少某些题的难度，递归问题一般使用迭代也能实现
• 分治，分治主要是减少问题的规模，分治的主要难点在于合并两个子问题的结果。
• 位运算，对于一些没有太好思路的题，位运算或许能收获到意想不到的后果。

参考别人总结的规律

• 如果问最短，最少，BFS(Breadth-first Search )
• 如果问连通性，静态就是 DFS(Depth-first Search),BFS，动态就 UF
• 如果问依赖性就 topo sort
• DAG 的问题就 dfs+memo
• 矩阵和 Array 通常都是 DP（Dynamic Programming）
• 问数量的通常都是 DP
• 问是否可以，也很有可能 DP
• 求所有解的，基本 backtracking
• 排序总是可以想一想的
• 万事总可以想 HashMap
• 找规律试试 Stack

来自 Leetcode 总结