C练题笔记之：Leetcode-70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/climbing-stairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1，既然题目是说能用动态规划解决，那么肯定有一定的规律在其中

自己先列举n为1~5的时候共有的方法数量：

1：1

2：2

3：3

4：5

5：8

由上可以发现，第五个的时候等于4和3的两种情况之和，4的时候是3和2的情况之和。那么由此可以构造出一个db表格。

2，构造db表：首先n = 1以下的时候就当只有1个方案。然后下面就是db[i] = db[ i - 2] + db[ i - 1];

int climbStairs(int n){
    int *db = (int *)malloc(sizeof(int) * (n+1));
    db[0] = 1;
    db[1] = 1;
    for(int i = 2; i <= n; i++) {
        db[i] = db[i-1] + db[i-2];
    }
    return db[n];
}