一天一道LeetCode

本系列文章已全部上传至我的github，地址：ZeeCoder‘s Github

欢迎大家关注我的新浪微博，我的新浪微博

欢迎转载，转载请注明出处

（一）题目

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

（二）解题

题目大意：从零开始每次跳一步或者两步，跳到N总共有多少种不同的跳法。

很典型的动态规划问题，状态转移方程为，dp[n] = dp[n-1]+dp[n-2]。

class Solution {
public:
    int climbStairs(int n) {
        int dp[n];//纪录跳到i的不同路径的个数
        if(n==0) return 1;//0的时候返回1
        if(n==1) return 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];//返回跳到n的次数
    }
};