DP动态规划中的“人人为我”与“我为人人”

在动态规划（DP）中，“人人为我”和“我为人人”是两种不同的状态转移思想，用于描述状态之间的依赖关系和更新方向：

1. 人人为我（Pull-based DP）

• 核心思想：当前状态的值 依赖于其他已知状态的值。

  即：用“周围点的值”来计算“当前点的值”。

• 实现方式：
  在计算状态 dp[i] 时，需要主动获取其他状态（如 dp[i-1]、dp[j]）的值，通过它们推导出 dp[i]。
• 典型场景：
  • 线性DP：如斐波那契数列 dp[i] = dp[i-1] + dp[i-2]。
  • 区间DP：如石子合并问题中，f[i][j] 的值依赖于子区间 f[i][k] 和 f[k+1][j] 的值 [3]。
• 特点：
  • 依赖前置状态：必须先计算所有依赖的子状态，才能计算当前状态。
  • 自然符合拓扑序：按依赖顺序递推（如从 i=0 到 i=n）。

示例：

# 斐波那契数列（人人为我）
dp[0] = 0; dp[1] = 1
for i in range(2, n+1):
    dp[i] = dp[i-1] + dp[i-2]  # 用 dp[i-1] 和 dp[i-2] 计算 dp[i]

2. 我为人人（Push-based DP）

• 核心思想：当前状态的值 主动更新其他状态的值。

  即：用“当前点的值”去更新“周围点的值”。

• 实现方式：
  计算完状态 dp[i] 后，立即用其值更新后续依赖它的状态（如 dp[i+1]、dp[j]）。
• 典型场景：
  • 最短路问题：如 Dijkstra 算法中，用当前节点更新邻居节点的距离。
  • 状态压缩DP：如旅行商问题（TSP）中，更新状态集合的代价 [6]。
• 特点：
  • 主动传播结果：状态计算后立即影响后续状态。
  • 需显式控制更新顺序：如按拓扑序或优先队列处理 [6]。

示例：

# 最短路径更新（我为人人）
dist[0] = 0
for u in graph.nodes:
    for v, w in graph.neighbors(u):
        # 用 dist[u] 更新 dist[v]
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w

关键区别

滚动数组优化

• 作用：用一维数组替代二维数组，节省空间（如 dp[2][n] → dp[n]）。
• 条件：
  • 仅当 旧值不再被使用 时可覆盖（如 dp[i][j] 只依赖 dp[i-1][k]）。
  • 常见于 人人为我 的线性DP（如斐波那契数列）[4]。
• 示例：

  dp[0], dp[1] = 0, 1
  for i in range(2, n+1):
      dp[i % 2] = dp[(i-1) % 2] + dp[(i-2) % 2]  # 交替覆盖旧值
  

总结

• 人人为我：当前状态的值由其他状态 推导而来（如“用邻居算自己”），适合依赖关系清晰的子问题分解 [4]。
• 我为人人：当前状态的值 主动影响 其他状态（如“用自己的值更新邻居”），适合状态间存在隐式依赖的优化问题 [6]。
  滚动数组是空间优化的技巧，需确保覆盖的数据不再使用，常用于 人人为我 型DP的迭代实现 [4]。