三角形-题解（递归+递推+图解）

每月月赛，最后一个周六晚八点开始，请提前预约参赛，参与排名！
混一天和努力一天，一天看不出任何差别，三天看不到任何变化，七天也看不到任何距离……
但是一个月后会看到话题不同，三个月后会看到气场不同，半年后会看到距离不同，一年后会看到人生道路截然不同。
通知：目前比赛栏的权限已经完全开放，支持老师、个人随时抽题创建比赛，需达到P2等级
比赛名称建议包含学校/组织名称，具有辨识度。不友好名称可能会被屏蔽，请大家知晓！
肺炎疫情，在家就是对社会最大的贡献！
Dotcpp编程网宣布为免费提供超过1500个的VIP账号供大家学习，以尽微薄之力！
团体及湖北地区优先，欢迎教师团体与管理员联系QQ2045302297
题库的题不仅仅支持C语言C++、java，Python和php也可以提交
编程小组功能上线！欢迎各位老师、社团协会小组负责人申请创建，方便教学、训练！
申请优质题解的标准第一，代码格式工整整齐，第二，不少于300字的思路讲解，有配图更佳！
代码格式工整、有详细说明和配图的题解才有更多的浏览哦
学习交流 QQ1群156740915、4群 364137421、 211300176、博主群487133400 Python小组群 783851273 验证信息备注网站昵称！
个人资料中有关于自己联系地址、联系电话的信息，用于我们邮寄奖品福利等，且信息不会公开，别人看不到，请大家知晓！
比赛创建功能已经完全开放，需要达到P2等级，写博客要达到P2等级
注意，恶意创建比赛、直接复制代码发布无营养题解的行为，将被禁止相应权限！并扣除经验值! 申请恢复请联系管理员解除
本站题解请在题目内页-我要写题解发布，这样可以出现在题目题解列表页，还可以申请加优增加曝光哦！

我不是ac王者

私信TA

用户名：pwj666

访问量：9890

签　名：

理想与现实的差距，差一个自律的自己。

等　　级
排　　名	32
经　　验	7290
参赛次数	11
文章发表	109
年　　龄	20
在职情况	学生
学　　校	lnu
专　　业	计算机科学与技术

　　自我简介：

自律给我自由。

TA的其他文章

C++结课设计-大整数类设计
浏览：35

02-线性结构--浙大数据结构-2019秋
浏览：24

03-树--浙大数据结构-2019秋
浏览：39

你可能喜欢

题解1142：【C语言训练】立方和不等式（C语言描述）
浏览：950

题解1061：C二级辅导-计负均正（C语言描述）
浏览：449

题解1055：C二级辅导-进制转换（C语言描述）
浏览：553

题解1133：【C语言训练】求1+2!+3!+...+N!的和（C++描述）
浏览：405

题解1041：C语言程序设计教程（第三版）课后习题9.8 （C语言描述）
浏览：433

优质题解三角形-题解（递归+递推+图解）

　　作者: 我不是ac王者　　　　发表时间：2019-10-11 13:49:12 浏览：436　|　评论：2　

原题链接：三角形

```目录 ```
```
1.典型的递归问题
2.递归解题思路：
3.暴力递归
4.递归树图解
5.自上而下 记忆化递归--时间优化
6.递推解题思路
7.二维数组--递推
8.图解
9.自下而上 填表式递推--空间优化
10.图解
11.递推法优化总结
12.关于递推和递归
```
```典型的递归问题： ```
```
D（r,j）:  第r行第j个数字（r,j从1开始算）。
MaxSum(r,j):   从D（r,j）到底边的各条路径中，最佳路径的数字之和。
问题：求MaxSum(1,1)
```

```递归解题思路： ```
```
D(r,j)出发，下一步只能走D（r+1,j）或者D(r+1,j+1)。
每次选取两者中较大的值，这样一来，每个子问题返回的结果都是最优的，那么结果必然也是最优的。

```
```
递归部分伪代码：
if(r==N) //边界条件
   MaxSum(r,j)=D(r,j);
else
   MaxSum(r,j)=Max{ MaxSum(r+1,j), MaxSum(r+1,j+1)  }+D(r,j);
```
然后就可以愉快的写出递归程序了
```暴力递归 ```
```
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 101
int D[MAX][MAX];
int n,T;
int MaxSum(int i,int j){
     if(i==n)
        return D[i][j];
     int x=MaxSum(i+1,j);
     int y=MaxSum(i+1,j+1);
     return max(x,y)+D[i][j];
}
int main(){
   int i,j;
   while(cin>>T){
        while(T--){
           cin>>n;
           for(i=1;i<=n;i++)
            for(j=1;j<=i;j++)
                cin>>D[i][j];
           cout<<MaxSum(1,1)<<endl;
        }
   }
   return 0;
}
```
等等，what?怎么时间超限了？
。。。。。。
因为存在大量的重复计算，严重影响程序的运行时间
用样例来看一下递归树是怎么样运行的
```递归树图解 ```
```
第一次 
```
![](/image_editor_upload/20191010094412_63585.png)
ps:第1个数是7，不是1这里错了，请注意
```
第二次
```
![](/image_editor_upload/20191010094648_11844.png)
ps:第1个数是7，不是1这里错了，请注意
```
最后一次
```
![](/image_editor_upload/20191010095645_33010.png)
```
从上图可知，
8->7 和 1->7 这个问题相同，都是计算7这个子问题；
3->1 和 8->1 这个问题相同，都是计算1这个子问题；
.......
可以看出，很多子问题被重复计算，为了避免重复计算，需要用数组储存中间子问题第一次计算出来的结果，每当需要这个子问题的结果时，只需要取出相应数组的值，不需要再次进行重复计算了，这样一来就可以很大程度优化时间复杂度了。
程序如下：
```
```自上而下 记忆化递归--时间优化 ```
```
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 101
int D[MAX][MAX];
int n,T;
int maxSum[MAX][MAX];
int MaxSum(int i,int j){
     if(maxSum[i][j]!=-1)return maxSum[i][j];//值不是-1，说明已经存下中间子问题的值
     if(i==n)
        return D[i][j];
     int x=MaxSum(i+1,j);
     int y=MaxSum(i+1,j+1);
     maxSum[i][j]=max(x,y)+D[i][j];
     return maxSum[i][j];
}
int main(){
   int i,j,k,t;
   while(cin>>T){
        while(T--){
           cin>>n;
           for(i=1;i<=n;i++)
            for(j=1;j<=i;j++){
                cin>>D[i][j];
                maxSum[i][j]=-1;//标记为-1
            }
           cout<<MaxSum(1,1)<<endl;
        }
   }
   return 0;
}
```
```
有自上而下的记忆化递归，自然也有自下而上的填表式递推。
有了上面总结出来的递推式，就可以直接推了，那么怎么推呢？
```
```递推解题思路 ```
```
用一个二维maxSum[i][j]储存数字三角形最底层一行的值，每次通过用最底层的最优值 来计算上一层的最优值。
其实就是记录中间过程的每一层的最优值。
```
```二维数组--递推 ```
```
#include<iostream>
#include<algorithm>
using namespace std;
int s[101][101],maxsum[101][101];
int main(){
	int n,c;
	while(cin>>c){
		while(c--)
		{ 
			cin>>n;
			for(int i=1;i<=n;i++)
				for(int j=1;j<=i;j++){
					cin>>s[i][j];
					maxsum[i][j]=0;
				}
			for(int j=1;j<=n;j++)
				maxsum[n][j]=s[n][j];  
		    for(int i=n-1;i>=1;i--){
		    	for(int j=1;j<=i;j++){
		    		maxsum[i][j]=max(maxsum[i+1][j],maxsum[i+1][j+1])+s[i][j];
				}
			}
			cout<<maxsum[1][1]<<endl;	
		} 	
	}	
	return 0;
}
```
```图解 ```
```
初始
```
![](/image_editor_upload/20191011011138_11269.png)
```
2
```
![](/image_editor_upload/20191011011223_24937.png)
```
3
```
![](/image_editor_upload/20191011011254_45369.png)
```
最后
```
![](/image_editor_upload/20191011011357_56935.png)
```
一般情况下，其实没必要用二维maxSum数组存储每一个计算出来的中间结果，只要从底层一行行向上递推，那么用一维数组maxSum[]即可。这里用s[][]向上滚动,本质和开一个一维数组向上滚动是一样的。
```
```自下而上 填表式递推--空间优化 ```
```
#include<iostream>
#include<algorithm>
using namespace std;
int s[101][101]; 
int main(){
	int n,c;
	while(cin>>c){
		while(c--){
			cin>>n;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=i;j++){
				cin>>s[i][j];
			}
		    for(int i=n-1;i>=1;i--){
		    	for(int j=1;j<=i;j++){
		    	s[i][j]=max(s[i+1][j],s[i+1][j+1])+s[i][j];
				}
			}
			cout<<s[1][1]<<endl;
		} 
	} 	
	return 0;
} 
```
```图解 ```

```
初始
```
![](/image_editor_upload/20191011012316_17699.png)
```
2
```
![](/image_editor_upload/20191011012411_60383.png)
```
3
```
![](/image_editor_upload/20191011012442_96432.png)
```
...
```
![](/image_editor_upload/20191011012536_36384.png)
```
最后
```
![](/image_editor_upload/20191011012915_71321.png)

```递推法优化总结 ```
```
从二维数组降到一维数组，空间复杂度是优化了，但是空间优化的代价是我们只能知道最终的结果，无法再回溯中间的选择。也就是说我们无法通过最终的结果来确定中间所走过的路径。具体情况具体分析用哪个。
```

------------

------------
```关于递推和递归 ```
```
其实我觉得没什么太大区别，时间上肯定是递推比递归快那么一丢丢，因为递推省去递归需要调用函数的时间开销，但是递归有时候写起来和理解起来也更容易一些，其实用哪个无所谓，哪个顺手用哪个。
```

0.0分

16 人评分