集团门户网站建设费用科目,wordpress5.0下载,如果做自己的网站,淘宝网络营销案例分析先找到规律#xff0c;然后找边界情况#xff1b;部分特殊情况分类讨论 *递归
70.爬楼梯
简单
提示
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢#xff1f;
示例 1#xff1a;
输入#xff1a…
先找到规律然后找边界情况部分特殊情况分类讨论 *递归
70.爬楼梯
简单
提示
假设你正在爬楼梯。需要 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
方法一动态规划 思路和算法
我们用 f(x) 表示爬到第 x 级台阶的方案数考虑最后一步可能跨了一级台阶也可能跨了两级台阶所以我们可以列出如下式子
f(x)f(x−1)f(x−2)
它意味着爬到第 x 级台阶的方案数是爬到第 x−1 级台阶的方案数和爬到第 x−2 级台阶的方案数的和。很好理解因为每次只能爬 1 级或 2 级所以 f(x) 只能从 f(x−1) 和 f(x−2) 转移过来而这里要统计方案总数我们就需要对这两项的贡献求和。
以上是动态规划的转移方程下面我们来讨论边界条件。我们是从第 0 级开始爬的所以从第 0 级爬到第 0 级我们可以看作只有一种方案即 f(0)1从第 0 级到第 1 级也只有一种方案即爬一级f(1)1。这两个作为边界条件就可以继续向后推导出第 n 级的正确结果。我们不妨写几项来验证一下根据转移方程得到 f(2)2f(3)3f(4)5……我们把这些情况都枚举出来发现计算的结果是正确的。
我们不难通过转移方程和边界条件给出一个时间复杂度和空间复杂度都是 O(n) 的实现但是由于这里的 f(x) 只和 f(x−1) 与 f(x−2) 有关所以我们可以用「滚动数组思想」把空间复杂度优化成 O(1)。下面的代码中给出的就是这种实现。 509. 斐波那契数
尝试过
简单
相关标签
相关企业
斐波那契数 通常用 F(n) 表示形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始后面的每一项数字都是前面两项数字的和。也就是
F(0) 0F(1) 1
F(n) F(n - 1) F(n - 2)其中 n 1给定 n 请计算 F(n) 。
这个就是只有第三个才开始变成斐波那契所以应该分类讨论
class Solution {public int fib(int n) {if(n2){return n;}int p0;int q0;int r1;for (int i2;in;i){pq;qr;rpq;}return r;}
} 1137. 第 N 个泰波那契数 泰波那契序列 Tn 定义如下
T0 0, T1 1, T2 1, 且在 n 0 的条件下 Tn3 Tn Tn1 Tn2
给你整数 n请返回第 n 个泰波那契数 Tn 的值。 示例 1
输入n 4
输出4
解释
T_3 0 1 1 2
T_4 1 1 2 4
class Solution {public int tribonacci(int n) {if (n0){return 0;}if (n2){return 1;}int i0,j0,k1,r1;//每次设定的时候保留一次for循环里的滚动一次即多一位0其实i是任意数字都没关系for (int m3;mn;m){//记得从第几个tri开始ij;jk;kr;rijk;}return r;}
}
