概览
DP之数字三角形基础题型
题解
dp问题
1. 状态表示
- 集合f[i, j]: 所有从(1, 1)到(i, j)的路径
- 属性: Min
2. 状态计算
- 集合划分: 由限制条件只能走2n-1步可知只有下或者右走
注意
Min问题注意初始化问题
一般来讲的思考方式是利用通用模板方式,其实有时间只注重为了怎么给f[0][i],f[i][0]初始化比较复杂,可以直接考虑
方法
1. 初始化f[0][i], f[i][0], 需要通用,往往不好考虑
2. 直接在代码计算时处理f[i][0], f[0][i], 更直观,只需要如何计算即可
另外地,通项的写法也有两种
- 一步, f[i][j] = min(f[i-1][j], f[i][j-1])
- 两步, 有时这样更简单
代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=110, INF=1e8;
int n;
int w[N][N];
int f[N][N];
int main() {
scanf("%d", &n);
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
scanf("%d", &w[i][j]);
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
if (i==1 && j==1) f[i][j] = w[i][j];
else {
f[i][j] = INF;
if (i > 1) f[i][j] = min(f[i][j], f[i-1][j] + w[i][j]);
if (j > 1) f[i][j] = min(f[i][j], f[i][j-1] + w[i][j]);
}
printf("%d\n". f[n][n]);
return 0;
}