爬楼梯

发表于
本文字数： 900 阅读时长 ≈ 1 分钟

LeetCode每日一题，70.Climbing Stiars

先看题目描述

题目大意是给定一个楼梯有 n 级，每次只能爬 1 级或 2 级，问有几种走楼梯方式

算法思路

这道题很简单，是个典型的动态规划类型题目

动态规划

  • 动态规划方程：dp[i] = dp[i - 1] + dp[i - 2]
  • 因为走完阶梯时，要么最后走了一步，要么最后走了两步，所以第 n 个阶梯的走完方式是第 n -1 个阶梯的走完方式与第 n - 2 个阶梯的走完方式之和
  • 最后返回 dp[n - 1]

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int climbStairs(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        int[] dp = new int[n];
        dp[0] = 1;
        dp[1] = 2;
        for (int i = 2; i < n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int climbStairs(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        int a = 1;
        int b = 2;
        int c = 2;
        for (int i = 2; i < n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}