一、记忆型递归

思路:将递归过程中已经计算过的结果存储起来,避免重复计算,从而降低时间复杂度。

例题如下:

数字三角形(例):

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

在上面的三角形中寻找一条从顶部到底边的路径,使得路径上所经过的数字之和最大。路径上的每一步都只能往下或者右下走。只需求出这个最大和即可,不要求输出具体路径。

三角形行数:(1-100)

数字范围(0-99)

普通递归

最容易想到的办法就是递归,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 105
int array[MAX][MAX];
int n;
int Max_Sum(int i,int j){
if(i==n)
return array[i][j];
else
return max(Max_Sum(i+1,j+1),Max_Sum(i+1,j)) + array[i][j];
}
int main(){
cin >> n;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= i;j++){
cin>>array[i][j];
}
}
cout<<Max_Sum(1,1)<<endl; //Prints: 30
return 0;
}

但是这个方法却有着极高的时间复杂度:2^n,原因就是因为进行了太多次重复计算,若按照题目所给的数据范围,时间复杂度最高将达到2^100,一定会严重超时,无法通过。

记忆型递归

记忆型递归的思路:将已经计算过的结果存储起来,避免多次重复计算,通过提高空间复杂度来降低时间复杂度。此题中,我们使用一个数组来存储已经计算好的结果。

记忆型递归代码如下:

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
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 105
int array[MAX][MAX];
int MaxSum[MAX][MAX];
int n;
int Max_Sum(int i,int j){
if(i==n)
return array[i][j];
/*-------if分割---------*/
if(MaxSum[i][j] != -1)
return MaxSum[i][j];
//如果存在记录,直接return该值
else
return MaxSum[i][j] = max(Max_Sum(i+1,j+1),Max_Sum(i+1,j)) + array[i][j];
//记录计算值并return
}
int main(){
cin >> n;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= i;j++){
cin>>array[i][j];
MaxSum[i][j] = -1; //标记,表示未计算
}
}
cout<<Max_Sum(1,1)<<endl; //Prints:30
return 0;
}

二、递归改递推

递推(一)

虽然递归是最容易想到的方法,但在动态规划问题中,对递推的使用要多于递归,用循环实现要比使用函数递归更加简洁,且时间复杂度更低。

对于本题:

  1. 由递归的终止条件可知,调用至第n行(最后一行)时,结果就是这个元素本身,即 return array[i][j];
  2. 从第n-1行开始的最大和结果可由第n行推出,第n-2行的结果可由n-1行的结果推出,依此类推。

因此,只需双重循环反向递推即可解答本题。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 105
int array[MAX][MAX];
int maxSum[MAX][MAX];
int n;

int main(){
cin >> n;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= i;j++){
cin>>array[i][j];
maxSum[i][j] = array[i][j];
}
}
for(int i = n-1;i >= 1;i--){
for(int j = i; j >= 1;j--){
maxSum[i][j] = array[i][j] + max(maxSum[i+1][j],maxSum[i+1][j+1]);
}
}
cout<<maxSum[1][1]<<endl; //Prints: 30
return 0;
}

递推(二)

上文中虽使用了递推方法来求解本题,使得时间复杂度进一步降低,但在空间复杂度上仍需要优化。

递推(一)可知:

  1. 每一步都需要且仅需要将前一次的结果累加
  2. 累加后,之前的所暂存的数据就失去作用

因此,仅需开辟一个一维数组就可以完成数据暂存:

1
int maxSum[MAX]; // MAX==105

将每一步的结果按列标累加到该数组即可。即:

1
2
3
4
5
6
7
8
9
10
11
for(int i=1;i<=n;i++){
maxSum[i] = array[n][i];
}
//将最后一行复制到暂存数组

for(int i = n-1;i >= 1;i--){
for(int j = 1; j <= i;j++){
maxSum[j] = array[i][j] + max(maxSum[j],maxSum[j+1]);
}
}
cout<<maxSum[1]<<endl; //Prints:30

即便如此,也还可以进一步优化,直接使用原数组的最后一行(第n行)暂存,空间复杂度将进一步降低。

代码如下:

1
2
3
4
5
6
for(int i = n-1;i >= 1;i--){
for(int j = 1; j <= i;j++){
array[n][j] = array[i][j] + max(array[n][j],array[n][j+1]);
}
}
cout<<array[n][1]<<endl; //Prints:30

总结

心累