力扣509 斐波那契数列 完全递归解法 / 设置备忘录减少递归次数解法 都是 自顶向下

public int fib(int n) {/** if(n<2){* return n;* }* else{* return fib(n-1) + fib(n-2);* }*/int[] memo = new int[n + 1];// 0-n 有效 存储计算出出来的 fib(n)return dp(memo, n);}public int dp(int[] memo, int n) {if (n == 1 || n == 0) {return n;} else {if (memo[n] != 0) {// 已经计算过的直接returnreturn memo[n];} else {memo[n] = dp(memo, n - 1) + dp(memo, n - 2);return memo[n];}}}

力扣 509 斐波那契数列 动态规划 自底向上

public int fib(int n) {if(n==0 || n==1){return n;}int temp1 = 0;int temp2 = 1;int tempR = 0;for(int i=2;i<=n;i++){tempR = temp1+temp2;temp1 = temp2;temp2 = tempR;}return tempR;}