本问题其实常规解法可以分成多个子问题，爬第 n 阶楼梯的方法数量，等于两个部分之和

1. 爬上 n−1 阶楼梯的方法数量。因为再爬 1 阶就能到第 n 阶
2. 爬上 n−2 阶楼梯的方法数量，因为再爬 2 阶就能到第 n 阶

所以我们得到公式 dp[n] = dp[n−1] + dp[n−2]
初始化 dp[0]=1 和 dp[1]=1
时间复杂度：O(n)

class Solution {public int climbStairs(int n) {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];}
}

最近做动态规划的题目，发现最重要的还是要能够拿着笔一步一步模拟，才能真正搞懂步骤