509. 斐波那契數

https://leetcode.cn/problems/fibonacci-number/

1. 確定dp數組（dp table）以及下標的含義 dp[i] 第i個斐波那契數值為dp[i]
2. 確定遞推公式 題目說了 F(n) = F(n - 1) + F(n - 2)
3. dp數組如何初始化 題目說了 F(0) = 0，F(1) = 1
4. 確定遍歷順序 從前向后遍歷
5. 舉例推導dp數組
6. 打印 dp 數組

• 我的答案

class Solution {public int fib(int n) {if(n==0) return 0;if(n==1) return 1;return fib(n-1)+fib(n-2);}
}

• 非遞歸

class Solution {public int fib(int n) {if (n <= 1) return n;             int[] dp = new int[n + 1];dp[0] = 0;dp[1] = 1;for (int index = 2; index <= n; index++){dp[index] = dp[index - 1] + dp[index - 2];}return dp[n];}
}

70. 爬樓梯

啊 沒思路

如果總共1階，有1種方法
如果總共2階，有2種方法

如果總共3階，他只可能是從1階或者2階上來的，1種+2種=3種方法。3階的前一個狀態只可能是2階或者1階段（一次走一步或者兩步），所以從初始到前一個階段共有3種方法。

如果總共4階，4階的前一個狀態只可能是2階或者3階段（一次走一步或者兩步），所以從初始狀態到上一階段，有2+3=5種

• 思考過程
  (1) 確定dp數組（dp table）以及下標的含義：達到第i階有 dp[i]種方法
  (2) 確定遞推公式 dp[i] = dp[i-1]+dp[i-2]
  (3) dp數組如何初始化 dp[1] = 1 ; dp[2] = 2
  (4) 確定遍歷順序 從前到后
  (5) 舉例推導dp數組
  (6) 打印 dp 數組

• AC

class Solution {public int climbStairs(int n) {if(n==1) return 1;if(n==2) return 2;int[]dp = new int[n+1];dp[1] = 1;dp[2] = 2;for(int i=3; i<=n; i++) {dp[i] = dp[i-1] + dp[i-2];}return dp[n];}
}

746. 使用最小花費爬樓梯

分析：
站在 0的位置，不花費錢，但是往上跳就要花費，【往上跳才需要花費】
頂樓的位置：數組長度+1

• 思考過程

(1) 確定dp數組（dp table）以及下標的含義：達到第i階，需要的花費為dp[i]
(2) 確定遞推公式 跳到dp[i]的前一個狀態有兩種 (1) dp[i-1]，(2) dp[i-2] ;
dp[i] = Math.min(dp[i-1] + cost[i-1] , dp[i-2] + cost[i-2])

(3) dp數組如何初始化 dp[0] = 0 ; dp[1] = 0
(4) 確定遍歷順序 從前到后
(5) 舉例推導dp數組
(6) 打印 dp 數組

• AC

class Solution {public int minCostClimbingStairs(int[] cost) {int top = cost.length;int[]dp = new int[top+1];dp[0]=dp[1]=0;for(int i=2; i<=top; i++) {dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);}return dp[top];}
}