动态规划和回溯算法区别

动态规划和回溯算法都是常用的算法，但在解题思路和应用场景上有一些区别。
1. 解题思路：
- 动态规划：通过维护一个表格（通常是一个二维数组），将问题划分为若干个子问题，并将子问题的解保存在表格中，最后利用保存的结果求解原问题。动态规划的关键是找到问题的状态转移方程，利用已解决的子问题的解来求解当前问题。
- 回溯算法：通过逐步构建解空间树，遍历所有可能的解，当找到一个解时，记录下来或者直接使用，然后回退到上一个节点，继续进行搜索。回溯算法的核心是遍历解空间和剪枝，以减少搜索空间。
2. 应用场景：
- 动态规划：适用于具有重叠子问题和最优子结构的问题，例如最长公共子序列问题、背包问题等。动态规划常用于求解最优化问题，通过保存已解决的子问题的解，避免重复计算，从而提高效率。
- 回溯算法：适用于在搜索问题的解空间时，需要遍历所有可能的解的场景。回溯算法常用于求解排列组合问题、图的遍历等。
3. 时间复杂度：
- 动态规划：通过保存子问题的解，避免重复计算，时间复杂度通常是子问题个数乘以求解每个子问题的时间复杂度。
- 回溯算法：需要遍历解空间的所有可能解，时间复杂度往往比较高，取决于解空间的规模。
虽然动态规划和回溯算法有一些共同点，但在解题思路、应用场景和时间复杂度上存在一些差异，根据具体的问题特点来选择相应的算法。

动态规划和回溯算法有以下区别：1. 动态规划是一种自底向上的算法思想，而回溯算法是一种自顶向下的算法思想。
2. 动态规划通过将问题分解为子问题，并将子问题的解存储起来，以避免重复计算，从而提高效率。
而回溯算法则是通过尝试所有可能的解决方案，直到找到满足条件的解。
3. 动态规划通常适用于具有重叠子问题和最优子结构性质的问题，而回溯算法适用于需要穷举所有可能解的问题。
4. 动态规划算法的时间复杂度通常较低，而回溯算法的时间复杂度较高，因为回溯算法需要遍历所有可能的解空间。
5. 动态规划算法的空间复杂度较高，因为需要存储子问题的解，而回溯算法的空间复杂度较低，因为只需要存储当前的解。
总结：动态规划和回溯算法在算法思想、解决问题的方式、时间复杂度和空间复杂度等方面存在明显的区别。
动态规划适用于具有最优子结构性质的问题，而回溯算法适用于需要穷举所有可能解的问题。

回溯算法虽好，但是复杂度高，即便消除一些冗余计算，也只是「剪枝」，没有本质的改进。而动态规划就比较玄学了，经过各种改造， 从一个加减法问题变成子集问题，又变成背包问题，经过各种套路写出解法，又搞出状态压缩，还得反向遍历。

转化为背包问题注重三个细节点：

dp[i][j] i 索引从1开始； j 可以从0开始遍历 —— 因为此处背包包含 0重量物品。 注意分情况状态转移： j>=nums[i-1] 回溯-> 动规问题转化 == 整体等式的推导 以及 问题转换时的0-1背包问题 。

「回溯算法」需要记录每一个步骤、每一个选择，用于回答所有具体解的问题；

「动态规划」需要记录的是每一个步骤、所有选择的汇总值（最大、最小或者计数）；

「贪心算法」由于适用的问题，每一个步骤只有一种选择，一般而言只需要记录与当前步骤相关的变量的值。