Leetcode刷题笔记(c++)

跳n个台阶为dp[n]跳法,那么先跳一个台阶剩下dp[n-1]跳法，先跳两个台阶剩下dp[n-2]跳法，则可以表示dp[n]=dp[n-1]+dp[n-2]

class Solution {
public:
    int numWays(int n) {
        if(!n)return 1;
        if(n==1)return 1;
        vectordp(n+1);
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=n;i++){
            if(dp[i-1]+dp[i-2]>1000000007)dp[i]=dp[i-1]-1000000007+dp[i-2];
            else dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};