DFS,BFS,DP的选择

宽度优先搜索（BFS）

• 适用场景：BFS适合用来解决“最短路径”问题，如在未加权图中找到两点之间的最短路径。它也适用于层次遍历树或图、搜索最小生成树等场景。
• 优点：BFS能够保证在找到解时，这个解是最优的（即路径最短的情况）。
• 缺点：在最坏情况下，需要存储所有访问过的节点，可能会消耗大量内存。

深度优先搜索（DFS）

• 适用场景：DFS适合用于需要探索所有可能路径的问题，如解迷宫、图的连通性、回溯算法中的排列、组合问题等。
• 优点：DFS的空间效率高于BFS，因为它的最大空间需求仅仅是递归的深度。
• 缺点：DFS可能会陷入死循环，需要特别处理避免重复访问。另外，它找到的路径不一定是最短的。

动态规划（DP）

• 适用场景：DP适用于解决有重叠子问题和最优子结构的问题，常见于求最值问题（如最长递增子序列、最大子数组和）、计数问题（如不同路径）等。
• 优点：DP可以通过存储子问题的解来避免重复计算，提高效率。
• 缺点：需要仔细设计状态和状态转移方程，有时候空间复杂度较高。

选择指导

1. 问题类型识别：首先识别问题类型，是寻找最短路径、需要遍历所有可能性还是有重叠子问题的最优化问题。
2. 数据规模考量：注意到算法的时间和空间复杂度，根据问题的数据规模来判断哪种算法更适用。
3. 边界条件处理：考虑问题的边界条件，这对于选择正确的算法和设计算法都非常重要。
4. 实现复杂度：有时候，实现起来更简单的算法即使在理论上效率低一些，也可能是更好的选择，因为它更容易避免实现中的错误。

数据规模启发

（n≤30用DFS或BFS，n≤100或n≤1000用DP）是一个基本的启发式方法，可以作为初步的算法选择指南，但要记住，最合适的算法总是取决于具体问题的性质。这个规则背后的思想是考虑到算法的时间复杂度和问题规模的关系。

为何n≤30适合DFS或BFS？

当n相对较小（如n≤30）时，问题的解空间不会特别大，这使得通过DFS或BFS穷举所有可能的解变得可行。DFS和BFS在这种规模的问题上能够较快地找到解，而且实现起来通常比较直接。

为何n≤100或n≤1000适合DP？

对于稍大的问题规模（如n≤100或n≤1000），直接的穷举变得不再可行，这时动态规划（DP）成为更好的选择。DP通过避免重复计算相同的子问题来优化计算过程，使得算法能够在可接受的时间内解决问题。

y总考前最后一次周赛给的技巧是 如果实在不确定 就直接写两套方案

手动if if(n≤30)执行暴搜 否则执行dp 这样能保证30以内的数据一定对 然后还能尽可能多拿后面的分

察觉dp

重叠子问题是什么？

在讨论DP时，“重叠子问题”是一个关键概念。如果在递归算法中，相同的问题被多次计算，那么这个问题就具有重叠子问题。简而言之，就是解决大问题需要反复解决一些相同的小问题。 （那就是记忆化搜索的意思了）

怎样察觉重叠子问题？

1. 递归结构：如果问题可以通过递归方式分解为更小的子问题，并且这些子问题中有很多是重复的，那么这个问题就可能有重叠子问题。比如，计算斐波那契数列中的某个数时，为了得到fib(n), 你需要计算fib(n-1)和fib(n-2)，而计算fib(n-1)又需要计算fib(n-2)和fib(n-3)，如此这般，fib(n-2)就被重复计算了多次。
2. 子问题的数量：当递归解决一个问题时，如果子问题的总数（不考虑重复）远小于递归过程中生成的总调用数量，那么这个问题很可能就有大量的重叠子问题。
3. 问题的描述：某些类型的问题，如路径问题（寻找从点A到点B的最短/最长路径）、分割问题（如将数字或字符串分割为满足某些条件的部分），经常会有重叠子问题。

有什么特征？

• 递归解法的效率低下：如果一个递归解法的执行时间远远高于其它方法，这可能是因为它在浪费时间重复计算相同的子问题。
• 可以通过分解问题为较小部分来解决：如果可以将问题分解成较小的部分，并且这些小部分之间存在明显的相似性，这就是重叠子问题的一个明显特征。

⬅️ DFS BFS相关模型 🏠 00-刷题理模型 ➡️ DFS