01背包：从DFS到DP

输入：

n, V = map(int, input().split())
v = [0] * 1010
w = [0] * 1010

for i in range(1, n+1):
    v[i], w[i] = map(int,input().split())

这五份代码展示了从递归（DFS）解法到动态规划（DP）表的逐步演变过程，体现了对01背包问题的优化思路。以下是分析和演变的详细过程：

第一份代码

特点：使用纯递归（DFS）解决问题，没有记忆化。

def dfs(x, spV):
    if x > n:
        return 0
    if spV < v[x]:
        return dfs(x + 1,spV)
    else:
        return max(dfs(x+1,spV),dfs(x+1,spV-v[x]) + w[x])

res = dfs(1,V)
print(res)

• 思想：
  通过递归尝试每个物品是否放入背包，逐层递归到底部返回最终结果。
• 问题：
• 存在重复计算：同一状态会被多次计算，导致时间复杂度指数级爆炸。
• 时间复杂度为 $O(2^n)$，对于大规模数据效率极低。

结论：
纯递归适合作为入门理解，但不可用于实际应用。需要通过记忆化搜索优化。

第二份代码

特点：递归 + 记忆化搜索。

mem = [[0] * 1010 for i in range(1010)]

def dfs(x, spV):
    if mem[x][spV]:
        return mem[x][spV] # 判断是否已经计算过
    sum = 0
    if x >n:
        sum = 0
    elif spV < v[x]:
        sum = dfs(x + 1,spV)
    else:
        sum = max(dfs(x+1,spV),dfs(x+1,spV-v[x]) + w[x])
    mem[x][spV] = sum
    return sum  # 保存结果

res = dfs(1,V)
print(res)

• 思想：
  在第一份代码的基础上，引入记忆化数组 mem[x][spV] 来存储状态结果，避免重复计算。
• 优点：
• 极大降低了递归调用次数，时间复杂度降至 $O(n \cdot V)$。
• 保留递归的直观思想，适合理解和实现。
• 问题：
  仍然使用递归，存在函数调用开销，代码运行速度不如纯动态规划。

结论：
递归 + 记忆化搜索是向动态规划过渡的重要阶段，是递归与DP的结合。

第三份代码

特点：二维DP表，自底向上迭代求解。

f = [[0] * 1010 for i in range(1010)]

for i in range(1, n+1):
    v[i], w[i] = map(int,input().split())

for i in range(n,0,-1):
    for j in range(V+1):
        if j < v[i]:
            f[i][j] = f[i-1][j]
        else:
            f[i][j] = max(f[i-1][j],f[i-1][j-v[i]] + w[i])

print(f[1][V])

• 思想：
  直接将递归状态转移转化为迭代，通过二维表 f[i][j] 存储每个状态结果。
• 转移方程：
• 当容量不足时：f[i][j] = f[i-1][j]
• 当容量足够时：f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i])
• 优点：
• 明确展示了DP的状态转移过程。
• 时间复杂度为 $O(n \cdot V)$，空间复杂度为 $O(n \cdot V)$。
• 问题：
• 空间利用不够优化，很多状态不需要保存。

结论：
二维DP是最基础的动态规划形式，为后续优化提供了理论基础。

第四份代码

特点：二维DP表，但改变了物品和容量的迭代方向。

f = [[0] * 1010 for i in range(1010)]

for i in range(1, n+1):
    v[i], w[i] = map(int,input().split())

for i in range(1,n+1):
    for j in range(V+1):
        if j < v[i]:
            f[i+1][j] = f[i][j]
        else:
            f[i+1][j] = max(f[i][j],f[i][j-v[i]] + w[i])

print(f[n+1][V])

• 区别：
• 第三份代码是从物品的最后一个状态向前推算，而这里是从第一个物品逐步推算。
• f[n+1][V] 表示最终结果，而非 f[1][V]。
• 优点：
  思路等价于第三份代码，但从开始方向推进，可能更符合部分人的理解习惯。

结论：
此代码和第三份代码在本质上无差别，只是迭代顺序的不同。

第五份代码

特点：一维DP优化，空间复杂度降低到 O(V)O(V)。

f = [0] * 1010

for i in range(1, n+1):
    for j in range(V, v[i]-1, -1):
        f[j] = max(f[j], f[j-v[i]] + w[i])

print(f[V])

• 思想：
  利用二维表的计算只依赖于上一行的状态，压缩成一维数组 f[j]。
• 优化点：
• 外层循环遍历物品，内层循环从右向左遍历容量（逆序确保不覆盖上一物品的状态）。
• 转移方程：
• 与二维表相同，只是状态存储在一维数组。
• 优点：
• 空间复杂度从 $O(n \cdot V)$ 降为 $O(V)$。
• 时间复杂度仍为 $O(n \cdot V)$，但空间节省显著。
• 问题：
  较二维表实现更抽象，不便于调试。

结论：
一维DP是01背包问题的最终优化形式，适合大规模数据。

代码演变的核心思想

1. 从递归到动态规划：
2. 递归解法 → 记忆化搜索 → 明确DP的状态转移关系。
3. 从二维表到一维表：
4. 利用状态间的依赖关系，逐步优化空间利用效率。
5. 空间与理解的权衡：
6. 二维表直观、易理解，但空间复杂。
7. 一维表高效，但实现较抽象，适合熟练掌握后使用。

学习建议

1. 理解递归与记忆化搜索：
   通过纯递归和记忆化递归，深刻理解状态转移公式的意义。

2. 练习二维动态规划：
   从二维表入手，逐步实现复杂问题。

3. 优化一维动态规划：
   熟悉一维DP的技巧，如逆序遍历容量避免状态覆盖。

4. 求最优子问题：

dfs(x) = max(dfs(x+1), dfs(x+2))

1. 求子问题的和：

dfs(x) = dfs(x+1) + dfs(x+2)