70. 爬樓梯 - 力扣（LeetCode）

/**

? ? ? ? 1階:1步,即1種; 2階:1步+1步或直接2步,即2種

? ? ? ? f(1) = 1,f(2) =2

? ? ? ? 3階:由1階邁2步,或2階邁一步; 4階:由2階邁2步,或3階1步; n階:由n-2階邁2步,或n-1階邁1步

? ? ? ? f(n) = f(n - 1) + f(n - 2)

*/

class Solution {/**1階:1步,即1種; 2階:1步+1步或直接2步,即2種f(1) = 1,f(2) =23階:由1階邁2步,或2階邁一步; 4階:由2階邁2步,或3階1步; n階:由n-2階邁2步,或n-1階邁1步f(n) = f(n - 1) + f(n - 2) *///記錄已經走過的臺階需要的方法數private List<Integer> memory = new ArrayList<>();public int climbStairs(int n) {//初始化,1階與2階可直接得出memory.add(1); //f(1) = 1;memory.add(2); //f(2) = 2;//return help(n);if(n <= 2) {return memory.get(n - 1);} for(int i = 3; i <= n; i++) {memory.add(memory.get(i - 2) + memory.get(i - 3));}return memory.get(memory.size() - 1);}private int help(int n) {if(memory.size() >= n) {return memory.get(n - 1);}if(n == 1 || n == 2) {return memory.get(n);} else {memory.add(help(n - 1) + help(n - 2));}return memory.get(memory.size() - 1);}
}