leetcode 70.爬楼梯 动态规划

题目描述

爬楼梯：原题链接
假设你正在爬楼梯。需要 $n$ 阶你才能到达楼顶。

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

---

思路

状态表示

$f[n]$:爬到第n阶台阶不同的方法的数量

属性

$sum$

状态转换

$f[n]=f[n-1]+f[n-2]$

第$n$阶台阶可以在第$n-1$台阶处再爬一个台阶
第$n$阶台阶也可以在第$n-2$台阶处再爬两个台阶

所以爬到第$n$阶台阶不同的方法的数量$=$爬到第$n-1$阶台阶不同的方法的数量$+$爬到第$n-2$阶台阶不同的方法的数量

初始状态

$f[0]=1$
$f[1]=1$：第一级台阶只可能是由第$0$级台阶跨一级这一种可能，所以为$1$

为什么会想到$f[0]=1$？
因为在计算$f[2]$的时候，通过状态转化方程，可以知道$f[2]=f[1]+f[0]$,而$2=1+1=0+1$，我们可以知道由第$0$级台阶跨两级台阶到第二级，也是一种方案，所以$f[0]=1$，这是通过反推，从而赋予意义.

---

代码

class Solution {
public:
    int climbStairs(int n) {
        int f[46];
        f[0]=1;
        f[1]=1;
        for(int i=2;i<=45;i++)
            f[i]=f[i-1]+f[i-2];
        return f[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11

---