暴力递归
public class Test {
public static void main(String
[] args
) {
for (int i
= 0; i
< 20; i
++) {
System
.out
.print(test(i
) + ",");
}
}
static int test(int a
) {
if (a
== 0 || a
== 1) return 1;
return test(a
- 1) + test(a
- 2);
}
}
带备忘录的递归解法
public class Test {
public static void main(String
[] args
) {
int[] mono
= new int[20];
for (int i
= 0; i
< 20; i
++) {
System
.out
.print(test(mono
, i
) + "\t");
}
}
static int test(int[] mono
, int a
) {
if (a
== 0 || a
== 1) return 1;
if (mono
[a
] != 0) return mono
[a
];
return test(mono
, a
- 1) + test(mono
, a
- 2);
}
}
dp数组的迭代解法
import java
.util
.Arrays
;
public class Test {
public static void main(String
[] args
) {
int[] dp
= new int[20];
dp
[0] = dp
[1] = 1;
for (int i
= 2; i
< 20; i
++) {
dp
[i
] = dp
[i
- 1] + dp
[i
- 2];
}
System
.out
.println(Arrays
.toString(dp
));
}
}
dp数组的迭代解法基础上进行状态压缩
public class Test {
public static void main(String
[] args
) {
for (int i
= 0; i
< 20; i
++) {
System
.out
.print(test(i
) + " ");
}
}
static int test(int a
) {
if (a
== 0 || a
== 1) return 1;
int pre
= 1;
int curr
= 1;
int sum
;
for (int i
= 1; i
< a
; i
++) {
sum
= pre
+ curr
;
pre
= curr
;
curr
= sum
;
}
return curr
;
}
}
相当于把DP table 的大小从 n 缩小到 2
