0-1背包

以0-1背包为例分享一下对于 “恰好”、“至多”、“至少”三种变形的理解和总结：假设数组为 nums，长度为n，总和为 target 对于正常的0-1背包问题(恰好-方案数)

# 记忆化搜索
def dfs(i,c):
  if i < 0:
    return 1 if c ==0 else 0
  if c < nums【i】:
    return dfs(i-1,c)
  return dfs(i-1,c)+dfs(i-1,c-nums【i】)
# 递推
f = 【1】+【0】* target
for i in range(n):
  num = nums【i】
  for j in range(target,num-1,-1)
    f【j】 = f【j】 +f【j-num】

对于方案数问题：

“恰好”问题边界为，仅 c==0 为1，其余为0 （1为合法，0为不合法情况）
“至多”问题边界为，c>=0 为 1，其余为0
“至少”问题边界为，c<=0为1，其余为0；

需要去除掉上述代码中“c < nums【i】”的约束，使 c 可以达到 0 及以下 f 数组在递推时，需要将下界调整至 0， for j in range(target,-1,-1) or for j in range(target+1) 对于dfs(i,c)，若 c<=0 则说明前i个数字选或不选都可以，即无约束；而在使用 f 数组进行存储时，f【0】通过循环式子可以保持为2^(i-1)，即记录了前i-1个数字选或不选的所有情况；因此，可以得到 f【j】 = f【j】 + f【max(j-num,0)】

对于极值问题，和方案数问题的差别主要在边界设置以及当前问题的处理上，由加操作变为了 min/max 操作对于正常的0-1背包问题(恰好-最大数)

def dfs(i,c):
  if i < 0:
    return 0 if c ==0 else -inf
  if c < nums【i】:
    return dfs(i-1,c)
  return max(dfs(i-1,c),dfs(i-1,c-nums【i】)+1)
# 递推
f = 【0】+【-inf】* target
for i in range(n):
  num = nums【i】
  for j in range(target,num-1,-1):
    f【j】 = max(f【j】,f【j-num】+1)

对于极值问题：

“恰好”问题边界为，仅 c==0 为0，其余为 inf/-inf （对应求最小/求最大的不合法情况）
“至多”问题边界为，c>=0 为 0，其余为 inf/-inf （对应求最小/求最大）
“至少”问题边界为，c<=0为0，其余为 inf/-inf （对应求最小/求最大）

需要去除掉上述代码中“c < nums【i】”的约束，使 c 可以达到 0 及以下 f 数组在递推时，需要将下界调整至 0， for j in range(target,-1,-1) or for j in range(target+1) 对于dfs(i,c)，若 c<=0 则说明前i个数字选或不选都可以；而在使用 f 数组进行存储时，f【0】通过循环式子记录了前i-1个数字选或不选的极值情况；因此，可以得到 f【j】 = f【j】 + f【max(j-num,0)】

完全背包