首页 > 代码库 > 每日编程-20170401
每日编程-20170401
题目:示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路 径,使该路径所经过的数字的总和最大。
每一步可沿左斜线向下或右斜线向下走;
1< 三角形行数< 25;
三角形中的数字为整数< 1000;
输入第一行为N,表示有N行 后面N行表示三角形每条路的路径权
输出路径所经过的数字的总和最大的答案
样例输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出
30
解答:
DP还是不太会啊,找了个最传统的练习一下
保存三角形后,从下向上算
倒数第二行,第一个数,它的选择只有最后一行的第一个和第二个数,选一个最大的加到自身
一行都算完,表示这一行的每个位置的最大的选择是多少
然后计算上一行
一直到第一行,就是第一行的最大的选择
1 #include <iostream> 2 #include <vector> 3 using namespace std; 4 int Max(int a, int b) { return a < b ? b : a; } 5 int triangleMax(vector<vector<int>> &v) { 6 for (auto i = v.size() - 2; i != -1; i--) 7 { 8 for (auto j = 0; j < v[i].size(); j++) 9 { 10 v[i][j] = v[i][j] + Max(v[i + 1][j], v[i + 1][j + 1]); 11 } 12 } 13 return v[0][0]; 14 } 15 int main() { 16 int n; 17 while (cin >> n) 18 { 19 vector<vector<int>> v; 20 vector<int> v2; 21 for (auto i = 0; i < n; i++) 22 { 23 for (auto j = 0; j < i + 1; j++) 24 { 25 int a; 26 cin >> a; 27 v2.push_back(a); 28 } 29 v.push_back(v2); 30 v2.clear(); 31 } 32 cout << triangleMax(v) << endl; 33 } 34 }
每日编程-20170401
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。