寻宝（动态规划dp）
寻宝
⼩明有⼀张藏宝图，上⾯有m*n个房间，每个房间⾥⾯都有⼀个有⼀定价值的宝物，⼩明只能从左上⾓的房间进⼊收集宝物，且每次只能向右边或向下边的房间继续寻宝，最终只能从最右下的房间出来。请你帮⼩明计算下他最多可以收集到多少价值的宝物？
mmap格式怎么打开输⼊格式:
输⼊第⼀⾏给出两个正整数m,n(1=<m,n<=2000)，随后给出m⾏数据，每⾏都包括n个正整数，中间⽤空格分割。
输出格式:
输出收集到的最⼤价值v，题⽬保证v<10^9。
输⼊样例:
4 4
1 18 9 3
7 10 6 12
5 13 4 15
2 11 8 16
输出样例:
78
代码：
#include<bits/stdc++.h>
using namespace std;
int mmap[2010][2010];
//藏宝图的数组下标从1开始，有利于寻宝。
int main(void){
int m,n;
cin>>m>>n;
for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
cin>>mmap[i][j];
}
}
//保证每⼀步都是从最⼤值点过来
for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
mmap[i][j]+= mmap[i-1][j]>mmap[i][j-1]?mmap[i-1][j]:mmap[i][j-1];
}
}
cout<<mmap[m][n];
}
动态规划思想
使⽤动态数组，确保⾛的每⼀步都能取得最⼤价值

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。