爬楼梯 - 简单

https://leetcode-cn.com/problems/climbing-stairs/

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

动态规划

由于第一步有1、2两种可能，那么可以得出，这时候千万别陷入递归的泥潭，而要考虑是否递归，一般而言，递归的两个分因子是独立的，而递推的两个分因子是有联系（如f（x-2）是构成f（x-1）的一个因子，，这时候应该考虑一下是否能够递推。

class Solution {
    public int climbStairs(int n) {
        if(n <= 0) return 0;
        int a = 1;
        int b = 1;
        int temp = 1;
        for (int i = 0; i < n - 1; i++) {
            temp = a + b;
            a = b;
            b = temp;
        }
        return temp;
    }
}

扩展：不能连续每次上两个台阶。，好好理解

看到图后，可能会有疑惑为什么不行。其实看你怎么理解这个函数吧，如果它表示输入求，输出能够爬到楼顶的方式的数量的话，那么很明显不对，因为第一步可以走两个台阶，而但是根据上图可以知道如果第一步走2个台阶，第2步只能走1个台阶，会把在该次函数中的第一步为2个阶梯的可能性也算上。看图，可以发现，右侧n-3结点可以走两个台阶；而且n结点到该n-3结点只有一条路，那么n结点右侧的所有道路，有n-3结点来决定，所以可以得到新的斐波那契数列。

递归法

超时：

class Solution {
    public int climbStairs(int n) {
        if(n < 0) return 0;
        return climb(n);
    }
    public static int climb(int n){
        if(n == 0) return 1;
        if(n < 0) return 0;
        return climb(n - 1) + climb(n - 2);
    }
}

枚举法：

1、每次走1阶
2、整个过程只有1次一次性走两个台阶
3、整个过程只有2次一次性走两个台阶
······
内存溢出：

public class ClimbingStair {
    public int climbStairs(int n) {
        if (n < 1) return 0;
        int result = 1;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n-1; i++) {
            list.add(i);
        }
        for (int i = 0; i < n / 2; i++) {
            list = climb(list, n);
            result += list.size();
        }
        return result;
    }
    public static List<Integer> climb(List<Integer> list, int len) {
        List<Integer> nlist = new ArrayList<>();
        int e;
        for (Integer integer : list) {
            e = integer + 2;
            while (e+1 < len) {
                nlist.add(e);
                e += 2;
            }
        }
        return nlist;
    }
}

某个阶梯多从重复，那么可以利用hashmap记录参数：

class Solution {
    public int climbStairs(int n) {
        if (n < 1) return 0;
        int result = n;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n - 1; i++) {
            map.put(i, 1);
        }
        for (int i = 1; i < n / 2; i++) {
            map = climb(map, n);
            for (int k : map.keySet()){
                result += map.get(k);
            }
        }
        return result;
    }
    public static Map<Integer, Integer> climb(Map<Integer, Integer> map, int len) {
        Map<Integer, Integer> nmap = new HashMap<>();
        int e;
        for (Map.Entry<Integer,Integer> entry : map.entrySet()){
            e = entry.getKey() + 2;
            while (e + 1 < len) {
                nmap.put(e,nmap.getOrDefault(e,0)+entry.getValue());
                e += 1;
            }
        }
        return nmap;
    }
}