数字三角形C++题解

文章目录

• 题目描述
• 题解
• 完整代码

如图所示，一个数字三角形。 请编一个程序计算从顶至底的某处的一条路 径，使该路径所经过的数字的总和最大。 　每一步可沿左斜线向下或右斜线向下走；

提示
1<三角形行数<25； 　三角形中的数字为整数<1000；
输入
第一行为N，表示有N行 后面N行表示三角形每条路的路径权

输出
路径所经过的数字的总和最大的答案

样例输入

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5


样例输出

30
题解

这道题是一道典型的DP数组题

首先需要2个for循环 分别是i和j
i的范围是从n-2一直重复到0
j的范围是从0到i
分别模拟的是从上到下的不停选择

for(int i=n-2;i>=0;i--)
for(int j=0;j<=i;j++)


可以向上走也可以往下走，所以我们就直接两种情况都考虑一下
最后就写出了这样的代码

for(int i=n-2;i>=0;i--){
for(int j=0;j<=i;j++){
dp[i][j]+=max(dp[i+1][j],dp[i+1][j+1]);
}
}


所以经过这样的循环，最后最大的和即为dp[0][0]

#include
using namespace std;
int dp[100][100];
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
for(int j=0;j<=i;j++)
scanf("%d",&dp[i][j]);
for(int i=n-2;i>=0;i--)
for(int j=0;j<=i;j++)
dp[i][j]+=max(dp[i+1][j],dp[i+1][j+1]);
printf("%d",dp[0][0]);

return 0;
}