概述
属于DP中数字三角形基础题型
方格中从(0,0)走到(m,n), 只能向下或向右走
题解
dp问题
集合角度进行考虑
- 状态表示
- 集合: f[i,j] 所有从(1,1)走到(i,j)的路线
- 属性:Max/Min/数量: 集合中每个元素和的最大值
> 注意Min一般需要注意初始化
- 状态计算
- 集合划分:考虑最后一步
> 往下或者往右走 - 划分依据: 整个计算的连通性
- 不重复:最值时不需要考虑
- 不漏
- 集合划分:考虑最后一步
代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
int n, m;
int w[N][N];
int f[N][N];
int main() {
int T;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
scanf("%d", &w[i][j]);
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
f[i][j] = max(f[i-1][j], f[i][j-1]) + w[i][j];
printf("%d\n", f[n][m]);
}
return 0;
}