前言
一旦写完一个可行的算法,便不想推倒重来,不知道有多少人和我一样有这样的想法。然而写完一个trash的递归算法,计算时间太慢固然也是不行的,这时记忆化递归可能会帮到你。
记忆化递归
记忆化递归的核心思想就是将已经算好的值给存起来,等再次需要用到的时候,就直接取而不用计算,这样就大大节省了计算时间。笔者认为,虽然看起来是用空间换时间,但是相比于每次都进行庞大的递归计算来说,用合理的空间存放之前求得的值是明智的。
思想很简单,实现起来其实也并不复杂,下面举例说明之。
例一:Leetcode119. 杨辉三角 II
简单描述:给定一个非负索引 rowIndex,返回「杨辉三角」的第 rowIndex 行。
普通递归(超时):1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21// author: SilenceZheng66
class Solution {
public int recusion(int pos, int rowIndex){
if(pos>rowIndex) return 0;
if(pos==rowIndex||pos==0) return 1;
return (recusion(pos-1, rowIndex-1) + recusion(pos, rowIndex-1));
}
public List<Integer> getRow(int rowIndex) {
ArrayList<Integer> ans = new ArrayList<>();
ans.add(1);
if(rowIndex==0) return ans;
for(int i=1;i<=rowIndex;i++){
if(i==rowIndex) ans.add(1);
else{
ans.add(recusion(i, rowIndex));
}
}
return ans;
}
}
利用对称(超时):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
32// author: SilenceZheng66
class Solution {
public int recusion(int pos, int rowIndex){
if(pos>rowIndex) return 0;
if(pos==rowIndex||pos==0) return 1;
return (recusion(pos-1, rowIndex-1) + recusion(pos, rowIndex-1));
}
public List<Integer> getRow(int rowIndex) {
ArrayList<Integer> ans = new ArrayList<>();
ans.add(1);
if(rowIndex==0) return ans;
int step = rowIndex/2;
for(int i=1;i<=step;i++){
ans.add(recusion(i, rowIndex));
}
if(rowIndex%2==0){
for(int i=step-1;i>=0;i--){
ans.add(ans.get(i));
}
}else{
for(int i=step;i>=0;i--){
ans.add(ans.get(i));
}
}
return ans;
}
}
记忆化递归+利用对称: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
32
33
34
35
36
37// author: SilenceZheng66
class Solution {
public int[][] rem = new int[34][34];
public int recusion(int pos, int rowIndex){
if(pos>rowIndex) return 0;
if(pos==rowIndex||pos==0) return 1;
if(rem[rowIndex][pos]!=0) return rem[rowIndex][pos];
rem[rowIndex][pos] = (recusion(pos-1, rowIndex-1) + recusion(pos, rowIndex-1));
return rem[rowIndex][pos];
}
public List<Integer> getRow(int rowIndex) {
ArrayList<Integer> ans = new ArrayList<>();
ans.add(1);
if(rowIndex==0) return ans;
int step = rowIndex/2;
for(int i=1;i<=step;i++){
ans.add(recusion(i, rowIndex));
}
if(rowIndex%2==0){
for(int i=step-1;i>=0;i--){
ans.add(ans.get(i));
}
}else{
for(int i=step;i>=0;i--){
ans.add(ans.get(i));
}
}
return ans;
}
}
后记
首发于 silencezheng.top,转载请注明出处。