我是靠谱客的博主 无情香水,这篇文章主要介绍力扣刷题之 青蛙跳台阶问题剑指 Offer 10- II. 青蛙跳台阶问题一、题目描述二、问题分析三、数据结构及算法分析四、总结五、完整源码,现在分享给大家,希望可以做个参考。

剑指 Offer 10- II. 青蛙跳台阶问题


文章目录

  • 剑指 Offer 10- II. 青蛙跳台阶问题
  • 一、题目描述
  • 二、问题分析
  • 三、数据结构及算法分析
    • 1.数据结构
    • 2.涉及算法
  • 四、总结
  • 五、完整源码


一、题目描述

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

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

原题链接:青蛙跳台阶问题


二、问题分析

动态规划:
青蛙跳 n 级台阶有两种情况:

  1. 跳 n-1 级台阶后,再跳1级台阶
  2. 跳 n-2 级台阶后,再跳2级台阶

即: f(n) = f(n-1) + f(n-2)

f(3) = f(2) + f(1)
f(2) = f(1) + f(0)
f(1) = 1
f(0) = 1

因此,得到递推公式:
f(n) = f(n-1) + f(n-2)


三、数据结构及算法分析

1.数据结构

2.涉及算法

利用递推公式有三种方法:

一、反序递归法
这种方法具有大量的重复计算,十分耗时,LeetCode也显示超时了。
代码实现如下:

if n <= 1:
	return 1
else:
	return dp(n-1) + dp(n-2)

时间复杂度:O(nn)
空间复杂度:O(1)

二、记忆化反序递归法
在普通反序递归法的基础上,设置一个数组记录已经计算得到的 f(0) ~ f(n),当重复遇到某个数值时可直接从数组取用,避免了重复的递归计算。
代码实现如下:

fn = [1, 1]
maxn = 1
if n <= 1:
	return fn[n]
elif maxn >= n:
	return fn[n]
else:
	fn.append(dp(n-1) + dp(n-2))
	maxn = n
	return fn[n]

时间复杂度:O(n)
空间复杂度:O(n)

三、动态规划法
根据递推公式计算状态转移方程
递推公式:f(n+1) = f(n) + f(n-1)
状态转移方程:f(n), f(n-1) = f '(n) + f '(n-1), f '(n)

根据状态转移方程从正序进行推导,中间只需要存储状态转移方程涉及到的数值。
初始化:f(n-1) = f(0) = 1, f(n) = f(1) = 1

代码实现如下:

if n <= 1:
	return 1
else:
	fn, fn_1 = 1, 1
	for _ in range(2, n + 1):
		fn_1, fn = fn, fn + fn_1
	return fn

时间复杂度:O(n)
空间复杂度:O(1)


四、总结

利用递推公式的三种方法:
一、递归法
二、记忆化递归法
三、动态规划:需要计算出状态转移方程


五、完整源码

class Solution:
    def numWays(self, n: int) -> int:
        if n <= 1:
            return 1
        else:
            fn, fn_1 = 1, 1
            for _ in range(2, n + 1):
                fn_1, fn = fn, fn + fn_1
            return fn % 1000000007

时间复杂度:O(n)
空间复杂度:O(1)


一 起 前 进

最后

以上就是无情香水最近收集整理的关于力扣刷题之 青蛙跳台阶问题剑指 Offer 10- II. 青蛙跳台阶问题一、题目描述二、问题分析三、数据结构及算法分析四、总结五、完整源码的全部内容,更多相关力扣刷题之内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(46)

评论列表共有 0 条评论

立即
投稿
返回
顶部