备忘录法
package DP;
//斐波那契 备忘录法
public class test1 {
public static void main(String[] args) {
Solution01 solution01 = new Solution01();
int a=solution01.Fibonacci(4);
System.out.println(a);
}
}
class Solution01 {
public int Fibonacci(int n) {
int Memo[]=new int[n+1];
for (int i = 0; i < Memo.length; i++) {
Memo[i]=-1;
}
return fib(n,Memo);
}
public int fib(int n,int Memo[]){
int res=0;
Memo[0]=0;
if (n==1){
Memo[n]=1;
res=Memo[n];
}
if (n>=2){
if (Memo[n]!=-1){
res=Memo[n];
}
else{
Memo[n]=fib(n-1,Memo)+fib(n-2,Memo);
res=Memo[n];
}
}
return res;
}
}
自底向上
public class Solution {
public int Fibonacci(int n) {
int Memo[]=new int[n+1];
Memo[0]=0;
Memo[1]=1;
for (int i = 2; i <=n; i++) {
Memo[i]=Memo[i-2]+Memo[i-1];
}
if (n<=0){
return n;
}
return Memo[n];
}
}
