寒光博客

[CC150]901:上楼梯
题目 A child is running up a staircase with n steps, and ca...
扫描右侧二维码阅读全文
29
2019/07

[CC150]901:上楼梯

题目

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));
    }
}

GitHub

本文作者:Author:     文章标题:[CC150]901:上楼梯
本文地址:https://dxoca.cn/Algorithm/201.html       百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:August 2nd, 2019 at 08:58 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment

One comment

  1. Dxoca

    链接: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]相加之后取模,使得全部结果没有溢出。