力扣刷题系列-70. 爬楼梯

题干题目分析代码实现

题干

原题链接

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

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

题目分析

本题是一道简单难度的动态规划，与力扣的按摩师，打家劫舍比较相似因为要求出有多少种方法可以爬到楼顶，所以状态设计为到第i阶台阶的方法数dp[i]因为每次只能爬1阶或者2阶，所以dp[i]只能由dp[i - 1]和dp[i - 2]决定，dp[i] = dp[i - 1] + dp[i - 2]，最后返回dp[n]即可该算法从时间上分析，只是遍历了一遍dp数组，所以时间复杂度为O(n)，空间上开辟了一个长度为n+1的数组，所以空间复杂度为O(n)

代码实现

class Solution { public int climbStairs(int n) { if(n == 0){ return 0; } int[] dp = new int[n + 1]; dp[0] = 1; dp[1] = 1; for(int i = 2; i <= n; ++i){ dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } }