记一次失败的题解

Starry_Coffee 发表于 2020-06-27 17:24:34
编辑于 2020-06-27 17:24:34

### 写在前面
本题难度为：简单；
为什么我不会：因为菜；
为什么错了还写出来：因为通过这题我又捡回了一点高中学过的东西，其实并不是毫无用处的；

那么题目描述及示例如下:

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
https://leetcode-cn.com/problems/climbing-stairs

示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶
## 以下思路完全跑偏，请勿模仿

首先想到一种情况，即每次都只爬1阶，有1种方法；
如果阶数为偶数的话还有一种情况，即每次都爬2阶，当然奇数阶没有这种情况；
由示例二可以想到，当n=3时，去掉第一种情况，还有两种情况，分别为1+2和2+1，实际上是交换了"爬1阶"和"爬两阶"这两件事的先后顺序;

n=3的情况已被示例给出，那不妨考虑一下n=4的情况:
(1)每次只爬1阶，情况为1+1+1+1，有1种方法；
(2)先按2个台阶爬一次，之后再按1阶爬，情况为2+1+1，观察可以发现，通过选择在哪里爬2个台阶，可以出现三种情况，即除了已给出的方法，还有1+2+1和1+1+2两种情况，共3种方法；
(3)只按2个台阶一次来爬，显然只有2+2一种方法；
综上，当n=4时，共有1+3+1=5种方法；

实际上我考虑的是n=5的情况，得出共有8种方法，但道理是一样的

回到(2)，可以发现这三种方法其实就是移动+2这一步在表达式中所在的位置，因为总共为三个数字相加，所有+2有三个位置可以移动；

这其实和三个小朋友坐三个座位是一样的，如果其中两个小朋友是完全相同的（大嘘），那么你会得到共有3种坐法，也就是B+A+A，A+B+A，A+A+B这样的三种；

这个思路其实就是排列组合里面的组合数，通过考虑C(3,2)（即三个座位，先选定两个座位给+1这一步，剩下的那一个位置自然是+2）来得到方法总数；
在此放一张组合数公式图：
![](https://ss1.bdstatic.com/70cFvXSh_Q1YnxGkpoWK1HF6hhy/it/u=1538283127,3070135654&fm=26&gp=0.jpg)
借助这个思路来分类讨论一下n=5的情况：
(1)每次只爬1阶，1种方法；
(2)有一次爬2阶，剩下3阶爬三次，一共爬了四次，然后选定三个位置安放+1或选择一个位置安放+2，共C(4,3)或C(4,1)共4种方法；
(3)有两次爬两阶，剩下1阶，一共爬了三次，可以得到C(3,2)或C(3,1)，即3种方法；
综上，n=5时共有C(5,5)+C(4,3)+C(3,2)=1+4+3=8种方法，可以发现，每有两个+1被替换成一个+2时，位置总数就会减少一个；
(注：这里采用从下往上读的读法，有些地区会采用从上往下读)

通过组合数的公式，可以得到这样一个函数：
`    int Combinations(int a, int b)//计算组合数C(a,b){`
        `if (!b) return 1;//C(a,0) = 1`
        `int num_b = 1, num_a = a;`
        `for (int i = 2; i <= b; i++) 
            num_b *= i;
        `
        `for (int i = a - 1; i > (a - b); i--) 
            num_a *= i;
        `
        `return num_a / num_b;`
    `}`
这个思路，每次计算组合数时都将两个+1换成+2来减少一个位置，所以n的值每次-1，于是有这个函数：
`int climbStairs(int n) {`
        `int ans = 0;`
        `for (int nums_1 = n; nums_1 >= 0; nums_1 -= 2) { //每次将两个1换成1个2`
            `ans += Combinations(n, nums_1);`
            `n -= 1; //合并会空一个位置出来`
        `}`
        `return ans;`
    `}`
所以这题的排列组合解法就是这样了，如果你把它当成一道老师留的课后练习题，那个时候它是对的；为什么说是错误解法呢，因为这个方法在n=13的时候就会溢出，即使通过改用unsigned long long也不能解决根本问题，用int的话在第10个测试用例n=35时就溢出了；

而其实这是一道动态规划的题，至于为什么我没用动态规划做，因为不会（菜  我  菜）；
其实我用的这个求组合数的方法都是菜的一批的，别骂了别骂了.jpg
看别人写的题解优雅而又简洁，我好酸（
其实当计算多种情况的时候，你会发现这是个斐波那契数列
##最后我将用一句LXNSNB来升华主题

Starry_Coffee

@Starry_Coffee