1.0-1背包问题：
#capacity :背包容量
#w[i]：第i个物体的体积
#v[i]：第i个物体的价值
def dfs(i , c): 定义：选或不选到第i个物体时，目前背包最大价值
i:目前装了i个物体 c：背包剩余容量
回溯公式：
dfs（i,c）=max(dfs(i-1,c),dfs(i-1,c-w[i])+v[i]) 装没装第i个物体的两种情况
边界条件：1.i == 0 没东西可装
2. 剩余容量不足以装下当前的这个w[ i ]
#capacity :背包容量 #w[i]：第i个物体的体积 #v[i]：第i个物体的价值 n = len(w) def dfs(i,c): if i < 0: return 0 if c < w[i]: return dfs(i-1,c) return max(dfs(i-1,c),dfs(i-1,c-w[i])+v[i]) dfs(n-1,capacity)1.1.目标和 问题
1.回溯法+cache
目标和问题可以转换为0-1背包问题，因为最后也是从数组中选出几个数，使其最终和为一个定值
令p：正数和，q：负数和 sums = p-q target = p+q
可以得出 p = （sum+target）//2 即几个数和为定值
dfs（i，t）定义：从i个数中选出和为t的 方案个数
参数i：从包括i及其往前的数字中选
t：现在要凑的目标和
回溯方程：
dfs(i,t) = dfs(i-1,t) + dfs(i-1,t-nums[i])
边界条件：若sum+target并不是偶数，或者为负数，那就无解，返回 0
边界条件：若当前的nums[i] > t，那就加不进去，return dfs(i-1,t)
初始条件：if i < 0: //没有可选的了，从n已经遍历到开头了
if t==0:return 1 此方案可行
else: return 0 没有恰好为t的方案
代码：
时间复杂度：t*n空间复杂度：：n
时间复杂度你可以把这个dfs函数的执行过程，理解成 “填一张 n 行、t 列的表格”：
class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: target = sum(nums)+target n = len(nums) if target%2 != 0 or target<0: return 0 t = target//2 @cache def dfs(i,t): if i<0: if t==0: return 1 else: return 0 if nums[i]>t: return dfs(i-1,t) return dfs(i-1,t) + dfs(i-1,t-nums[i]) return dfs(n-1,t)2.递推
先根据回溯公式写出f公式：
dfs(i,t) = dfs(i-1,t) + dfs(i-1,t-nums[i])
f[i][t] = f[i-1][t] + f[i-1][t-nums[i]]数组最好不要出现负数情况
f [ i + 1 ] [ t ] = f [ i ] [ t ] + f [ i ] [ t - nums[ i ] ]
于是自然想到建立一个f[[]]二维数组 为了边界条件，我们的二维数组会多一列、一行
公式：f = [ [0] *(t +1) for _ in range(n+1) ] *的是列数量 for的是行数量
n+1对于前0个，1个...n个元素
t 对应 凑出和为0 ，1 ，...t的数
递归变循环，怎么变，取决于f公式需要什么
f [ i + 1 ] [ t ] = f [ i ] [ t ] + f [ i ] [ t - nums[ i ] ] 可以看出需要 i ， t , nums[ i ]
for i,x in enumerate(nums):
for c in range(t+1):
边界条件：nums[i]>t: 在这就是 x>c
时间复杂度：t n 空间复杂度 t n
class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: target = sum(nums)+target n = len(nums) if target%2 != 0 or target<0: return 0 t = target//2 f = [[0]*(t+1)for _ in range(n+1)] f[0][0]=1 for i,x in enumerate(nums): for c in range(t+1): if x>c: f[i+1][c] = f[i][c] else: f[i+1][c] = f[i][c]+f[i][c-x] return f[n][t]3.空间优化两个数组
发现f[i+1]只取决于f[i]，所以只需要两个数字
之后的数组重新覆盖f0和f1即可
f = [[0]*(t+1)for _ in range(2)] 两行数组
f[i+1]都改成f[(i+1)%2]
f[i]都改成f[i%2]
空间复杂度为 t
4.空间优化一个数组
和i有关的都删掉，遍历target的时候倒着遍历，从t遍历至x，倒序到 x，只处理 c≥x 的场景，避免重复选，最开始的边界条件
时间复杂度 tn 空间复杂度t
class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: target = sum(nums)+target n = len(nums) if target%2 != 0 or target<0: return 0 t = target//2 f =[0]*(t+1) f[0]=1 for x in nums: for c in range(t,x-1,-1): f[c] = f[c]+f[c-x] return f[t]2.完全背包
每个物品可以重复选，回溯公式修改：
dfs（i,c）=max(dfs(i-1,c),dfs(i-1, c-w[i])+v[i])
dfs (i,c) = min(dfs(i-1,c),dfs(i, c-w[i])+v[i])选了，但还可以选，所以i不变
2.1 零钱兑换
1.回溯法+cache
dfs(i,c)定义：用前i种硬币，凑c块钱，最少用几个硬币
i：前i种硬币
c:还需要凑c块钱
回溯方程：
dfs(i,c) = min(dfs(i-1,c) + dfs(i-,c-coins[i])+1)
边界条件：
1.若 coins[i]>c，return dfs(i-1,c) 这类硬币滚蛋
2.若i < 0 andc!=0，说明还没凑完，return inf 无解
起始条件：
若 i<0 and c==0,return 0所有硬币都处理完了，且剩余要凑的金额是 0不需要再用任何硬币
i < 0且c == 0→ 返回 0
- 含义：所有硬币都处理完了，且剩余要凑的金额是 0（已经凑够了）；
- 为什么返回 0？因为 “没有硬币可选” 的情况下，凑够了金额 0，不需要再用任何硬币→ 最少硬币数就是 0；
- 举例子：比如你要凑金额 0，不管有没有硬币，都只需要 0 个硬币（啥都不用选），这是所有最值问题的 “基础锚点”。
class Solution: def coinChange(self, coins: List[int], amount: int) -> int: n = len(coins) @cache def dfs(i,c): if i<0: if c==0:return 0 else: return inf if coins[i] > c: return dfs(i-1,c) return min(dfs(i-1,c),dfs(i,c-coins[i])+1) ans = dfs(n-1,amount) if ans < inf: return ans else: return -1
