纯数字三角形模型
- 状态表示:
(i, j)表示到达当前位置的最后一步如何, 共有两种状态
f[i - 1][j], f[i][j]
- 状态转移:
f[i][j] = max(f[i-1][j - 1] + q[i][j], f[i][j] + q[i][j])
- 可能需要注意边界条件: 比如最左边的列, 和最上面的行
对应AcWing题号：
数字三角形的变形
这类变形形式, 主要是走几次，中间最后一步不同
- 状态表示:
(n, i1, i1)表示走了n步，i1路径和i2路径, 总共有四种状态
f[k][i1 - 1][i2 - 1]
f[k][i1][i2]
f[k][i1 - 1][i2]
f[k][i1 - 1][i2 - 1]
- 状态转移:
int& t = f[k - 1][i1 - 1][i2];
x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);
x = max(x, f[k - 1][i1 - 1][i2] + t);
x = max(x, f[k - 1][i1][i2 - 1] + t);
x = max(x, f[k - 1][i1][i2] + t);
- 注意当两条路径相同的时候只需要加一次
对应的acwing题目
标签：状态,i1,max,模型,i2,三角形,动态,AcWing From： https://www.cnblogs.com/zhengel/p/16776715.html