剑指 offer 变态跳台阶（DP）

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

Solution

时间复杂度O(n^2)：

a[n]=a[n-1]+a[n-2]+......+a[1]+a[0]其中a[0]=a[1]=1,a[2]=2。

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        res = [None] * (100 + 1)
        res[0] = res[1] = 1
        res[2] = 2
        for i in range(3, 100+1):
            res[i] = sum(res[:i])
        return res[number]

时间复杂度O(n)：

但是上述代码时间复杂度达到O(n^2),空间复杂度也达到O(n),重新看一下上述结论：

a[n]=a[n-1]+a[n-2]+......+a[1]+a[0];..........................①
a[n-1]=        a[n-2]+......+a[1]+a[0];..........................②
两式相减可知：a[n]=2*a[n-1];

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        res = [None] * (100 + 1)
        res[0] = res[1] = 1
        for i in range(2, 100+1):
            res[i] = 2*res[i-1]
        return res[number]

最后

以上就是彩色老虎最近收集整理的关于剑指 offer 变态跳台阶（DP）的全部内容，更多相关剑指内容请搜索靠谱客的其他文章。