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

```目录 ```
```
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分

8 人评分