动态规划----1.爬楼梯

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);}
}