LeetCode70. Climbing Stairs

1、题目链接

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

2、解题思路

这道题是说有n阶台阶，让你从第0阶开始走到第n阶，有一个条件：

• 每次必须走1-2阶

问你有多少种方式能走完整个台阶，这是一道很经典的动态规划题目，而动态规划的思想就是将一个大的问题，划分为若干个子问题；由于题目中告诉你每次只能走1或者2步，那么第n阶台阶的上一步有可能是第n-1阶，也有可能是n-2阶，所以第n阶台阶的走法会等于第n-1阶与第n-2阶的和，依次类推。

3、代码

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;  //当两个阶梯的时候，可以用0-1-2，也可以直接0-2，有两种方法
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

4、结果

1564136762111.jpg