刷题之路：1216 - 【基础】数塔问题（递推求解）题解 - 码农知识堂

刷题之路：1216 - 【基础】数塔问题（递推求解）题解
题目描述
有如下所示的数塔，要求从底层走到顶层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？
输入
输入数据首先包括一个整数整数N(1 <= N <= 100)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间[0,99]内。

输出
从底层走到顶层经过的数字的最大和是多少？

样例
输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出
30
大家好，我是屁孩君，今天跟大家一起分享一道递推的题，数塔问题。
解题过程
- 解题思路
- 分步完成
  完整代码
解题思路

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
我们的思路呢是把除了第n行，其他元素都变成经过此元素最大值，从n-1层开始遍历，把每行的元素的正下方的元素与正下方的右边的元素进行比大小，然后把大数加上，以此类推，直到第一行的值求出来后。
简单的来说就是，每个元素，都要找一个人做伙伴，他只能找他的正下方与正下方右边的元素做朋友，他们都十分贪心，都想要自己的伙伴值越大越好，找到自己的伙伴后两人的值就会相加，求的就是，哪几个元素作伙伴的值最大。这样总懂了吧。
大家可以用这张图对照这上面的图进行对比，更好的理解思路。

分步完成

1.输入
```
这大家总会吧
1
```
2.判断是自己的正下方的元素大还是正下方的右边的元素大，哪个大就把他加上
```
if(a[i+1][j]
```
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
3.输出最上面的元素的值
```
......这就不用我写了吧
1
```
完整代码

话不多说，直接上完整代码！！！
```
#include
using namespace std;
int a[110][110];//二维数组
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			cin>>a[i][j];
		 } 
	}
	for(int i=n-1;i>=1;i--)//最后一行不用遍历
	{
		for(int j=1;j<=i;j++)//遍历每行的元素
		{
			if(a[i+1][j]
```
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
收工！！！
接下来的几天呢，屁孩君会陆续更新一些关于递归的题！！！希望对大家有用！多多支持！！！
今天屁孩君就给大家分享到这了！！！
古德拜！！！
记得三连哦！！！

刷题之路：1216 - 【基础】数塔问题（递推求解）题解

解题过程

解题思路

分步完成

完整代码