【算法题解】 Day11 数学
70. 爬楼梯
题目
70. 爬楼梯 难度：easy
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入： n = 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶提示：
1 <= n <= 45
方法一：数学
思路
根据题意，可以知道这是斐波那契数列，那就直接套用公式：
接着我们就可以通过这个公式直接求第 n 项了。
解题
Python：
class Solution:
def climbStairs(self, n: int) -> int:
import math
sqrt5 = 5 ** 0.5
fibn = math.pow((1 + sqrt5) / 2, n + 1) - math.pow((1 - sqrt5) / 2, n + 1)
return int(fibn / sqrt5)Java：
public class Solution {
public int climbStairs(int n) {
double sqrt5 = Math.sqrt(5);
double fibn = Math.pow((1 + sqrt5) / 2, n + 1) - Math.pow((1 - sqrt5) / 2, n + 1);
return (int) Math.round(fibn / sqrt5);
}
}方法二：动态规划
思路
根据题意，需要爬 n 阶楼梯才能到达楼顶，并且每次只能爬1或2个台阶，问有几种方法？
这里可以采用逆向思维，即跨越最后一步或者两步就到达了楼顶，这样如此反复进行逆推，因此可以总结出如下公式：
f(n)=f(n−1)+f(n−2)f(n)
它意味着爬到第 n 级台阶的方案数是爬到第 n−1 级台阶的方案数和爬到第 n−2 级台阶的方案数的和。很好理解，因为每次只能爬 1 级或 2 级，所以 f(n) 只能从 f(n - 1) 和 f(n - 2) 转移过来，而这里要统计方案总数，我们就需要对这两项的贡献求和。
以上是动态规划的转移方程，下面我们来讨论边界条件。我们是从第 0 级开始爬的，所以从第 0 级爬到第 0 级我们可以看作只有一种方案，即 f(0) = 1；从第 0 级到第 1 级也只有一种方案，即爬一级，f(1) = 1。这两个作为边界条件就可以继续向后推导出第 n 级的正确结果。
p = 0
q = 0
r = 1
for ...:
p = q
q = r
r = p + q
解题
Python：
class Solution:
def climbStairs(self, n: int) -> int:
res = [1, 2]
if n <= 2:
return res[n-1]
for i in range(2, n):
res.append(res[-1] + res[-2])
return res[-1]Java：
class Solution {
public int fib(int n) {
if (n < 2) {
return n;
}
int p = 0, q = 0, r = 1;
for (int i = 2; i <= n; ++i) {
p = q;
q = r;
r = p + q;
}
return r;
}
}509. 斐波那契数
题目
509. 斐波那契数 难度：easy
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1给定 n ，请计算 F(n) 。
示例 1：
输入： n = 2
输出： 1
解释： F(2) = F(1) + F(0) = 1 + 0 = 1示例 2：
输入： n = 3
输出： 2
解释： F(3) = F(2) + F(1) = 1 + 1 = 2示例 3：
输入： n = 4
输出： 3
解释： F(4) = F(3) + F(2) = 2 + 1 = 3提示：
0 <= n <= 30
方法一：数学
思路
参照上题思路；
解题
Python：
class Solution:
def fib(self, n: int) -> int:
sqrt5 = 5**0.5
fibN = ((1 + sqrt5) / 2) ** n - ((1 - sqrt5) / 2) ** n
return round(fibN / sqrt5)Java：
class Solution {
public int fib(int n) {
double sqrt5 = Math.sqrt(5);
double fibN = Math.pow((1 + sqrt5) / 2, n) - Math.pow((1 - sqrt5) / 2, n);
return (int) Math.round(fibN / sqrt5);
}
}方法二：动态规划
思路
参照上题思路；
解题
Python：
class Solution:
def fib(self, n: int) -> int:
if n < 2:
return n
p, q, r = 0, 0, 1
for i in range(2, n + 1):
p, q = q, r
r = p + q
return rJava：
class Solution {
public int fib(int n) {
if (n < 2) {
return n;
}
int p = 0, q = 0, r = 1;
for (int i = 2; i <= n; ++i) {
p = q;
q = r;
r = p + q;
}
return r;
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-10-09，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录