比较backtracking跟dp

楼主在刷dp的题目,发现很多dp的题目都可以用backtracking解. 感觉backtracking跟dp 貌似就是一个题目的两个解法. 想问问大家有没有什么好的模板可以做到backtracking 跟dp 互换的.
比如下面这一题.
https://leetcode.com/problems/partition-to-k-equal-sum-subsets/
用backtracking就很好想,dp真的不怎么会.
谢谢大家.好的共享会加米的.

backtracking 解题很直观 但是可能会导致栈溢出，DP没有这个问题, DP需要找出转移方程 这个更需要逻辑思维

回溯会tle鸭，dp就是用空间换性能

你理解不太对
DP一般会有个状态方程 可以用iteration或者recursion + mem两种写法
backtracking是另外一个东西 一般用recursion写
他们会有一些本质区别的 backtracking更接近search

dp一定会有重复的子问题的
backtracking不是

dp分top-down和bottom-up，你说的backtracking应该是指recursion和caching实现的top-down approach

zhmingrui 发表于 2021-7-11 06:02
dp分top-down和bottom-up，你说的backtracking应该是指recursion和caching实现的top-down approach

的确是这么回事