70.Climbing Stairs

递归解决方法

public class Main {
    int sum = 0;

    public int climbStairs(int n) {
        if (n <= 0) {//
            sum++;

        } else if (n == 1) {
            sum++;
        } else {
            climbStairs(n - 1);//每一种结果都有两种选择 要么一步 要么两步
            climbStairs(n - 2);
        }

        return sum;
    }
    public static void main(String[]args) {
        Main m=new Main();
        System.out.println(m.climbStairs(2));
    }
}

非递归

public class Main {
    int sum = 0;

    public int climbStairs(int n) {
        if (n <= 1) {
            return 1;
        } else {
            int[] arr = new int[n];
            arr[0] = 1;
            arr[1] = 2;
            int i = 2;
            while (i = 2) {
                arr[i ] = arr[i-1] + arr[i - 2];//每一个都是前两位之和 
                i++;

            }
            return arr[n - 1];
        }
    }

    public static void main(String[] args) {
        Main m = new Main();
        System.out.println(m.climbStairs(8));
    }
}

其他人解法也是大同小异

private int[] memo;

public int climbStairs(int n) {
    memo = new int[n + 1];
    Arrays.fill(memo, -1);
    return getClimbStairs(n);
}

private int getClimbStairs(int n) {
    if (n == 1) {
        return 1;
    }

    if (n == 2) {
        return 2;
    }

    if (memo[n] == -1) {
        memo[n] = getClimbStairs(n - 1) + getClimbStairs(n - 2);
    }
    return memo[n];
}
}

int climbStairs(int n){

int x1=0,x2=1;
int i;
int sum;
for(i=1;i<=n;i++)
{
    sum=x1+x2;
    x1=x2;
    x2=sum;
}
return sum;
}

哈希表 有趣

public class Solution {

int result;
HashMap memo = new HashMap();

public int climbStairs(int n) {
    if(n < 2) {
        return 1;
    }
    if(memo.containsKey(n)) {
        return memo.get(n);
    }
    result = climbStairs(n-1) + climbStairs(n-2);
    memo.put(n,result);
    return result;
}
}