题目
A child is running up a staircase with n steps, and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child
can run up the stairs.
大意
让你上n级的楼梯,每次可以走1,2,3级,3种选择,那么走到n级一共有几种组合
题解
通过 递归和 迭代(数学归纳)来解决
递归的表现力根强 但是算法的复杂度较高。
前者O(3^n) 后者 O(n)

package CC150;
public class _901_上楼梯 {
static int count = 0;
/**
* 递归
* n较小的时候会超时 效率低
* 倒着写 顺这看
* O(3^n)
*
* @param n
* @return
*/
public static int rec(int n) {
if (n <= 0) return 0;
if (n == 1) return 1;
if (n == 2) return 2;
if (n == 3) return 4;
return rec(n - 1) + rec(n - 2) + rec(n - 3);
}
/**
* 迭代法 通过数学规律
* 1 2 4 7 13 24
* O(n)
* @param n
* @return
*/
public static int inter(int n) {
if (n <= 0) return 0;
if (n == 1) return 1;
if (n == 2) return 2;
if (n == 3) return 4;
int x1=1;
int x2=2;
int x3=4;
for (int i = 4; i <= n; i++) {
int x_1=x1;
x1=x2;
x2=x3;
x3=x_1+x1+x2;//递推公式 n=(n-1)+(n-2)-(n-3)
}
return x3;
}
public static void main(String[] args) {
System.out.println(rec(10));
System.out.println(inter(10));
}
}
本文作者:Author: 寒光博客
文章标题:[CC150]901:上楼梯
本文地址:https://dxoca.cn/Algorithm/201.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
本文地址:https://dxoca.cn/Algorithm/201.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
链接:https://www.nowcoder.com/questionTerminal/7f0661ace6df48d0af3f924950d57126
a[i]=((a[i-1]+a[i-2])%1000000007+a[i-3])%1000000007
的解释:
取模运算有这样一个性质:(a+b)%c = ((a%c)+(b%c))%c
所以(a[i-1]+a[i-2])%1000000007就相当于(a[i-1]%X+a[i-2]%X)%X 用X代替1000000007
这样就使得a[i-1]、a[i-2]、a[i-1]+a[i-2]都没有溢出,之后再与a[i-3]相加之后取模,使得全部结果没有溢出。