刷题记录-0309

图论算法
最小生成树，Prim算法。
图的最短路径问题：Djkstra算法，解决单个点到全图所有点的最短路径问题，例题lc743 网络延迟时间。还有floyd算法，所有点到所有点的最短路径算法

动态规划：有些dp可以拆分成树形结构，然后再用memo或者用dp去递推关系，注意有些问题需要从尾部开始dfs，如最长递增子序列。有些无法拆分成树形结构，如编辑距离，分割等和子集（可以拆成树，但不好记录memo），，此时需要去仔细拆分子问题，来寻找递推。

背包问题：
0-1背包：可以拆dfs，但因为每个数只能用1次，不利于dfs时记录2维memo。最好还是dp来做。示例分割等和子集
完全背包：零钱兑换。每个数可以用多次，可以用dfs + memo来做

动态规划：

1. lc279 完全平方数, 可以用dp来做，也可以用dfs的backtrack来做；
2. lc139 单词拆分。
3. lc300 最长递增子序列，dp来做；dfs的话从尾部开始遍历，这样可以记录memo

二维动态规划：
1. lc72 编辑距离，不太好拆解dfs，也是通过把source和target字符串拆解为小的，一步步来做；二维dp

lc42 接雨水：暴力解法，memo解法，双指针解法。双指针解法空间复杂度O(1)，主要是依赖，每个点的更新，取决于左右两边最大值的最小值。