0
已解决
中级天翼
题目描述 Description
芬里尔喵终于击败了邪恶的奥丁。他手持着昆古尼尔，在英灵殿中寻找宝物。英灵殿可以看成是一个m*n个格子组成的巨大房间。英灵殿的宝器太多了，芬里尔喵给每个格子的宝器分配了一个价值，w[i][j]。芬里尔喵最初处在巨大房间的左上角，她朝着右下角的出口寻觅。由于英灵殿的魔法力量的封印，她每次只能朝右方或者下方前进。请你帮她计算一下，最后总共最多能获得的宝器的价值是多少。
输入描述 Input Description
第一行，两个整数，m n
接下来m行，第i行有n个空格隔开的整数，第j个值表示w[i][j]
输出描述 Output Description
最多能获得的宝器的总价值
样例输入 Sample Input
5 5 1 5 4 10 15 2 32 6 8 17 15 26 3 18 34 3 6 9 12 16 1 21 10 4 16
样例输出 Sample Output
151
数据范围及提示 Data Size & Hint
m, n<=10
李牧晓在2022-05-04 21:08:13追加了内容
已自行解决~
1
已采纳
初级天翼
递推边界:
如果(i==1&&j==1) f[i][j]=a[i][j];
否则如果(i==1) f[i][j]=f[i][j-1]+a[i][j];
否则如果(j==1) f[i][j]=f[i-1][j]+a[i][j];
递推关系:
f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j];
目标 ：
f[m][n]
0
中级天翼
ding
0
中级天翼
ding
