动态规划和回溯算法区别_数据库

资料来源：网络整理时间：2023/3/5 13:16:24 共计：3602 浏览

动态规划和回溯算法区别？

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

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

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

版权说明：
本网站凡注明“广州京杭原创”的皆为本站原创文章，如需转载请注明出处！
本网转载皆注明出处，遵循行业规范，如发现作品内容版权或其它问题的，请与我们联系处理！
欢迎扫描右侧微信二维码与我们联系。