在一座山上,有很多很多珠宝,它们散落在山底通往山顶的每条道路上,不同道路上的珠宝的数目也各不相同.下图为一张藏宝地图:
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
”夺宝奇兵”从山下出发,到达山顶,如何选路才能得到最多的珠宝呢?在上图所示例子中,按照5-> 7-> 8-> 3-> 7的顺序,将得到最大值30样例输入
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5样例输出:
30
典型的动态规划问题,最后所取得的结果总与前一个有关;采用从后面开始算起的方法,从倒数第二层开始,倒数第二层能取得的最大值由倒数第一层决定,挑选它的前一层的最大的值,刷新自身的值为自己的值加上前一层它能取到的最大的值,不断循环直到回到第一层,输出其结果
#include<iostream> #include<algorithm> using namespace std; const int n = 110; int f[n][n]; int main() { int m; cin >> m; for (int i = 1; i <= m; i++) { for (int j = 1; j <= i; j++) { cin >> f[i][j]; } } for (int i = m-1; i>=1; i--) { for (int j = 1; j<=i; j++) { f[i-1][j] += max(f[i][j], f[i][j+1]); } } cout << f[1][1]<<endl; }