leetcode排位赛 Interview Study Guide 学习Leetcode问题的注意事项

leetcode排位赛面试学习指南资源动态规划与回溯与动态规划的比较动态规划和回溯有许多相似之处和不同之处，并且在第一次学习它们时经常会混淆。通常，混淆仅来自名称冲突，其中DP的一部分涉及“回溯”以在DP末尾重新创建最佳解决方案序列。例如，当在DP中找到通过网格的最小路径时，我们可能希望最小化所采取的跳跃次数，但要重建最终路径，我们通常需要从最终解决方案向后退，以回溯使我们到达的所有步骤最优点以重构最小路径。这不是回溯算法。在回溯中，我们通过应用局部变换并收集我们在进行中找到的解决方案来详尽地搜索解决方案空间。它被命名为“回溯”，因为我们需要退出我们对当前解决方案所做的每个局部转换，以便继续搜索其余空间。想象一下搜索迷宫时您没有任何信息，因此您唯一的选择是搜索所有路径。当然，您会在身后留下一连串碎屑，这样一旦遇到死胡同，您就可以沿着碎屑返回到第一个位置，在那里您可以做出不同的决定，即道路上的所有岔路口。您可以继续这样做，直到您探索了迷宫中的所有可能路径。它与DP相似，因为我们正在穷尽地搜索解决方案空间，以保证我们将触及所有重要的解决方