算法：共n阶台阶，每次上1或2阶，有几种上法？

> 本文是从我的CSDN搬运过来的：[共n阶台阶，每次上1或2阶，有几种上法？](https://blog.csdn.net/hu18315778112/article/details/126135125)

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

![在这里插入图片描述](https://images.oldmoon.top/images/dingdangdog/dingdangdog-1682480074441.jpeg)

<!-- more -->

## 做答过程

### 测试示例：

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

### 1、普通递归法（错误）

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

#### 代码
```java
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级，基本的搭配就这三种，先确定这三种搭配，再对每种搭配进行排序即可。

#### 代码
```java
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、使用排列组合公式、并优化

- 在第二种写法时，递归的时候，就已经觉得是高中时学的排列组合问题了，由于一时没想起来公式是啥，就没有去实践。但结果仍然不对，那就只能去思考使用高中的排列组合公式能否可行。
- 排列公式：本题中不适用排列公式
- ![在这里插入图片描述](https://images.oldmoon.top/images/dingdangdog/dingdangdog-1682480134188.png)

- 组合公式：其中阶乘式比较适合使用，转化为本题，公式中`n`就是走1级次数和走2级次数的总和，`m`可以是1级次数或2级次数，结果相同。
- ![在这里插入图片描述](https://images.oldmoon.top/images/dingdangdog/dingdangdog-1682480149449.png)

#### 基本排列组合
```java
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级台阶次数。

```java
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;
    }

}
```
## 总结

结果很不幸，当天没有去认真回忆排列组合公式，导致没有写完优化后这种方案，最后没有提交结果，不知道最后的答案是否正确。

感悟：
- 1、很多问题用初中高中的知识就能解决，可惜你都忘了。
- 2、有些问题不要死磕，网上查查，能节省很多时间。
- 3、算法真难。-.-