2024-03-23 15:06 已编辑 南京理工大学 算法工程师
关注
刷题记录-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)，主要是依赖，每个点的更新，取决于左右两边最大值的最小值。
最小生成树，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)，主要是依赖，每个点的更新，取决于左右两边最大值的最小值。
全部评论
相关推荐
点赞 评论 收藏
分享
04-24 11:13
电子科技大学 后端 
一枚大铁锤：至于冲不冲小红书，这是个问题，我先声明我不是这方面的专家，我觉得这件事还是要慎重评论，你问我为什么不给出回答，因为我一开始就说了，我不是这方面的专家 点赞 评论 收藏
分享