当前位置：网站首页>共n级台阶，每次可以上1级或2级台阶，有多少种上法？

共n级台阶，每次可以上1级或2级台阶，有多少种上法？

2022-08-04 02:03:00 【Xxhu1997】

CSDN每日一练题目

2022-08-02日CSDN每日一练中等难度题目。
题目要求 1 <= N <= 50，当输入N后在一秒钟之内计算出结果。
题目类型：递归、循环

做答过程

测试示例：

n = 3 , 正确结果为 3
n = 4 , 正确结果为 5
n = 5 , 正确结果为 8
n = 6 , 正确结果为13

1、普通递归法

刚开始思路不是很明确，就随便写写，写出个递归，但是当N较大时，计算效率极低。

代码

class Main {
    
    public static void main(String[] args) {
    
        System.out.println(System.currentTimeMillis());
        int n = 50;
        int result = solution(n);

        System.out.println(result);
        System.out.println(System.currentTimeMillis());

    }

    public static int solution(int n) {
    
        int result = 0;

        if (n >= 1 && n <= 2){
    
            result = n;
        } else {
    
            result = solution(n -1) + solution(n - 2);
        }

        return result;
    }

}

结果

因为计算时间较长，官方没有说明计算结果是否正确，只是说明超时。

2、递归优化

第一种递归效率很低，所以想着优化递归。
优化思路：因为只能走1级或2级台阶，那么可以先确定走1级和2级总的搭配种类，举例说明：如共5级台阶，那么可以先确定1和2的搭配方式有：5次1级、3次1级和1次2级、1次1级和2次2级。先不管第几步做1级或2级，基本的搭配就这三种，先确定这三种搭配，再对每种搭配进行排序即可。

代码

class Main {
    
    public static void main(String[] args) {
    
        System.out.println(System.currentTimeMillis());
        int n = 20;
        int result = solution(n);

        System.out.println(result);
        System.out.println(System.currentTimeMillis());

    }

    public static int solution(int n) {
    
        int result = 0;
        for (int oneNum = n; oneNum >= 0; oneNum--) {
    
            if ((n - oneNum) % 2 == 0) {
    
                result += countNum(oneNum, (n - oneNum) / 2);
            }
        }
        return result;
    }

    public static int countNum(int oneNum, int twoNum) {
    
        if (oneNum == 0 || twoNum == 0) {
    
            return 1;
        } else if (oneNum == 1 || twoNum == 1) {
    
            return oneNum + twoNum;
        }
        int total = 0;

        for (int i = 0; i <= oneNum; i++) {
    
            if (oneNum - i == 0) {
    
                total += 1;
            } else {
    
                total += countNum(oneNum - i, twoNum - 1);
            }
        }

        return total;
    }
}

结果

虽然优化有一定的效果，但当N较大时依然很慢，所以这种写法还不是答案。

3、使用排列组合公式、并优化

在第二种写法时，递归的时候，就已经觉得是高中时学的排列组合问题了，由于一时没想起来公式是啥，就没有去实践。但结果仍然不对，那就只能去思考使用高中的排列组合公式能否可行。
排列公式：本题中不适用排列公式
组合公式：其中阶乘式比较适合使用，转化为本题，公式中n就是走1级次数和走2级次数的总和，m可以是1级次数或2级次数，结果相同。

基本排列组合

class Main {
    
    public static void main(String[] args) {
    
        System.out.println(System.currentTimeMillis());
        int n = 20;
        int result = solution(n);

        System.out.println(result);
        System.out.println(System.currentTimeMillis());

    }

    public static int solution(int n) {
    
        int result = 0;
        for (int oneNum = n; oneNum >= 0; oneNum--) {
    
            if ((n - oneNum) % 2 == 0) {
    
                result += countNum(oneNum, (n - oneNum) / 2);
            }
        }
        return result;
    }
    public static int countNum(int oneNum, int twoNum) {
    
        if (oneNum == 0 || twoNum == 0) {
    
            return 1;
        } else if (oneNum == 1 || twoNum == 1) {
    
            return oneNum + twoNum;
        }
        int total = 0;
        int top = 1;
        for (int i = oneNum + twoNum; i > 1; i--) {
    
            top *= i;
        }

        int down = 1;
        for (int i = oneNum; i > 1; i--) {
    
            down *= i;
        }
        for (int i = twoNum; i > 1; i--) {
    
            down *= i;
        }
        total = top / down;

        return total;
    }

}

结果

使用此代码测试，当N过大时，计算无法正常执行，会报错，原因是当N过大时，阶乘后数字过大，超出类型存储数字范围，导致数字变成0，最终导致分母为0计算出错。

优化公式计算逻辑

优化思路：
1、先对公式进行约分，减小阶乘数值
2、m选取较小的数字，如果走1级台阶的次数小，就将1级台阶次数置为m，反之则是2级台阶次数。

class Main {
    
    public static void main(String[] args) {
    
        System.out.println(System.currentTimeMillis());
        int n = 20;
        int result = solution(n);

        System.out.println(result);
        System.out.println(System.currentTimeMillis());

    }

    public static int solution(int n) {
    
        int result = 0;
        for (int oneNum = n; oneNum >= 0; oneNum--) {
    
            if ((n - oneNum) % 2 == 0) {
    
                result += countNum(oneNum, (n - oneNum) / 2);
            }
        }
        return result;
    }

    public static int countNum(int oneNum, int twoNum) {
    
        if (oneNum == 0 || twoNum == 0) {
    
            return 1;
        } else if (oneNum == 1 || twoNum == 1) {
    
            return oneNum + twoNum;
        }
        int total = 0;
        int topMin = 1;
        int downMax = 1;
        if (oneNum > twoNum) {
    
            topMin = oneNum;
            downMax = twoNum;
        } else {
    
            topMin = twoNum;
            downMax = oneNum;
        }
        int top = 1;
        for (int i = oneNum + twoNum; i > topMin; i--) {
    
            top *= i;
        }

        int down = 1;
        for (int i = downMax; i > 1; i--) {
    
            down *= i;
        }
        total = top / down;

        return total;
    }

}