题目
- 原题地址：数字三角形
- 题目编号：505
- 目标算法：dp（动态规划）
1.题目大意
- 金字塔形三角形，每个位置一个数，求顶部到底部路径中，每个数加起来的最大值
- 要求：向左下走和向右下走的次数相差不能超过 1。
2.题目分析
- 由于向左下走和向右下走的次数相差不能超过 1，所以可以推断出符合题意的答案只能是最后一行中间位置的一个或两个。
①dfs做法
思路
- 当走到最后一行的中间位置就返回，回来的时候挑大的一路
- （硬凑的，原理还是dp的）
时空复杂度分析
②dp做法
思路
- 从第二行开始逐行向下遍历，每行加上一行对应的两个中最大的（最前和最后特判）
- 答案就是最后一行最中间的一个（或两个中的最大值）
时空复杂度分析
- 时间复杂度：O((1+n)*n/2)
- 空间复杂度：O(1)
3.题目代码
①dfs做法
点击查看代码
#include
using namespace std;
int a[105][105];
int n;
int dfs(int line, int pos)
{
if(line==n-1)
if(n%2==1)
if(pos==(n+1)/2)
return a[line][pos] + a[line+1][pos];
else if(pos+1==(n+1)/2)
return a[line][pos] + a[line+1][pos+1];
else
return -INT_MAX;
if(n%2==0)
if(pos==n/2)
return a[line][pos] + max(a[line+1][pos],a[line+1][pos+1]);
else
return -INT_MAX;
else
return a[line][pos] + max(dfs(line+1,pos),dfs(line+1,pos+1));
}
int main()
{
cin >> n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
cin >> a[i][j];
}
if(n==1)
cout << a[1][1] << endl;
else
{
int ans = dfs(1,1);
cout << ans << endl;
}
return 0;
}
②dp做法
点击查看代码
#include
using namespace std;
int a[105][105];
int dp[105][105];
int n;
int main()
{
cin >> n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
cin >> a[i][j];
}
dp[1][1] = a[1][1];
for(int i=2;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
if(j==1)
dp[i][j] = a[i][j] + dp[i-1][1];
else if(j==i)
dp[i][j] = a[i][j] + dp[i-1][i-1];
else
dp[i][j] = a[i][j] + max(dp[i-1][j],dp[i-1][j-1]);
}
}
cout << max(dp[n][(n+1)/2],dp[n][(n+2)/2]) << endl;
return 0;
}