【力扣每日一题】——爬楼梯

一、题目描述

原题链接
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶

二、题目分析

如果用递归进行求解的话，在进行递归运算时存在大量的重复计算，我们假设递归树的深度为n，则结点数为2^n 因此时间复杂度为O( n^2)。如果n的值稍微大一些我们的程序就会运行超时。因此我们用动态规划来优化代码。
求解
首先我们先确定DP的状态和转移方程

• 状态变量： dp[n]表示爬n阶台阶的所有可能情况的总和
• 状态转移方程： dp(n) = dp(n-1) +dp(n-2)
• 初始条件： dp(0)=0
• 边界条件： 因为n是正整数，故不需要考虑n<0的情况，等于n即终止状态转移方程

我们每次进行计算后就保存计算结果，这样保证每次计算都只是计算一次，继而解决重复计算的问题。

三、代码实现

class Solution {
    public int climbStairs(int n) {
        //特判，防止n=1时dp[2]下标越界
         if (n==1) {
            return 1;        
        }
        //定义数组用来存储每次计算的结果
    int[] dp=new int[n+1];
        dp[1]=1;
        dp[2]=2;
        for (int i = 3; i <= n; i++) {
            //状态转移方程
            dp[i]=dp[i-1]+dp[i-2]; 
        }
        return dp[n];
    }
}