题目描述
给定一个如下图所示的数字三角形,从顶部出发,在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点,一直走到底层,要求找出一条路径,使路径上的数字的和最大。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输入格式
第一行包含整数 n,表示数字三角形的层数。接下来 n行,每行包含若干整数,其中第 i
行表示数字三角形第 i 层包含的整数。
输出格式
输出一个整数,表示最大的路径数字和。
数据范围
1≤n≤500,
−10000≤三角形中的整数≤10000
样例
输入样例:
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出样例:
30
算法1
(回溯)
因为是回溯,基本上枚举了所有情况,这样的复杂度比较高,会超时的。
但是这里我还是写上来,主要是回溯有回溯的好处,比如我可以直接输出这个最大的路径或者最小的路径,或者某个路径的和等于某个值,这样的话,回溯是可以实现的
C++ 代码
#include <iostream>
#include <vector>
#include <cstring>
#include <sstream>
using namespace std;
void maxpath(const vector<vector<int>>& datas, int idx, int col, int& sum, int& res)
{
if(idx == datas.size())
{
res = max(res, sum);
return ;
}
sum += datas[idx][col];
maxpath(datas, idx + 1, col, sum, res);
sum -= datas[idx][col];
if(col + 1 >= datas[idx].size()) return ; // 越界判断(不要以为下一行比这一行多就可以省)
sum += datas[idx][col + 1];
maxpath(datas, idx + 1, col + 1, sum, res);
sum -= datas[idx][col + 1];
}
int main()
{
int n, ans = 0, sum = 0;
cin >> n;
getchar();
vector<vector<int>> datas(n);
for(int i = 0; i < n; ++i)
{
string line; // 用变量i来决定每行的vector容量,但是这样通用一点
getline(cin, line);
istringstream iss(line);
int num;
while(iss >> num)
datas[i].push_back(num);
}
maxpath(datas, 0, 0, sum, ans);
cout << ans << endl;
return 0;
}
算法2
(动态规划)
自下向上求解
C++ 代码
#include <iostream>
#include <vector>
#include <cstring>
#include <sstream>
using namespace std;
int main()
{
int n;
cin >> n;
getchar();
vector<vector<int>> vec(n);
for(int i = 0; i < n; ++i)
{
string str;
int val;
getline(cin, str);
istringstream iss(str);
while(iss >> val)
vec[i].push_back(val);
}
for(int i = n - 2; i >= 0; --i)
for(int j = 0; j < vec[i].size(); ++j)
vec[i][j] += max(vec[i + 1][j], vec[i + 1][j + 1]);
cout << vec[0][0] << endl;
return 0;
}