动态规划之上楼梯

案例一：有n级台阶，一个人每次上一级或者两级，问有多少种走完n级台阶的方法。为了防止溢出，请将结果Mod 1000000007

给定一个正整数int n，请返回一个数，代表上楼的方式数。保证n小于等于100000。
测试样例：
1
返回：1

暴力搜索法code

# -*- coding:utf-8 -*-
class GoUpstairs:
    def countWays(self, n):
        # write code here
        # 暴力搜索法
        res = 0
        if n==0:
            return 1
        if n<0:
            return 0
        else:
            res+=self.countWays(n-1)
            res+=self.countWays(n-2)
        return res


###运行结果：
您的代码已保存
答案错误:您提交的程序没有通过所有的测试用例
case通过率为11.76%

用例:
36196

对应输出应该为:

811714518

你的输出为:

maximum recursion depth exceeded

记忆搜索法code：

class GoUpstairs:
    def countWays(self, n):
        # write code here
        # 记忆搜索法
        dp = [0]*(n+1)
        res = 0
        if n==0:
            return 1
        if n<0:
            return 0
        else:
            if dp[n]!=0:
                if dp[n]!=-1:
                    return dp[n]
                else:
                    return 0
            else:
                res+=self.countWays(n-1)
                res+=self.countWays(n-2)
        if res==0:
            dp[n]=-1
        else:
            dp[n]=res
        return res

### 输出：
您的代码已保存
内存超限:您的程序使用了超过限制的内存
case通过率为0.00%

用空间换时间后发现超出内存范围

动态规划方法：

class GoUpstairs:
    def countWays(self, n):
        # write code here
        # 记忆搜索法
        dp = [0]*(n+1)
        dp[0]=1
        dp[1]=1
        for i in range(2,n+1):
            dp[i]=(dp[i-1]+dp[i-2])%1000000007
        return dp[n]