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));
}