dp深似海

“系统过去的历史只能通过现阶段的状态去影响系统的未来”——研究生算法课程老师对动态规划的描述，感觉挺不错的

分类参考了灵神的dp题单

记忆化搜索和递推是dp的两种实现方式

注意事项

如果动态转移方程不是按顺序的，那么需要注意不能直接赋值f[i+1][j] = f[i][j];，因为这样可能会覆盖之前动态转移的结果（注释的是按顺序的动态转移写法）

相关题解：3276. 选择矩阵中单元格的最大得分

1
2
3
4
5
6
7
f[i+1][j] = Math.max(f[i+1][j], f[i][j]);
// f[i+1][j] = f[i][j];  // 这里是错的，不能赋值
for (int s = map.get(nums.get(i)), t = 0; s > 0; s -= t) {
    t = s & -s;
    if ((j & t) > 0) continue;
    f[i+1][j|t] = Math.max(f[i+1][j|t], f[i][j] + nums.get(i));
}

刷表法和查表法

在动态规划中，根据转移来源计算状态叫查表法（最常见），用当前状态更新其他状态叫刷表法。

  • 2140. 解决智力问题(1709)：刷表法和查表法两种写法
  • 3524. 求出数组的 X 值 I：刷表法（刷表法：如果枚举 x，倒推 x=y⋅vmodk 中的 y，是困难的。但枚举 y，计算 y⋅vmodk，是简单的。也就是说，对于状态 f[i+1][x] 而言，其转移来源是谁不好计算，但从 f[i][y] 转移到的目标状态 f[i+1][y⋅vmodk] 是好计算的。）