05 走楼梯(递归)

题目大意是有n阶楼梯，可以一次走两级，也可以一次走n级。问走到第n阶一共有多少走法。

分析： 这种递归题目一般都是要先分析状态转移的过程。
首先边界条件： n = 1 只有一种走法 n = 2 有两种走法。
转移方程: 因为第n阶楼梯只可能由第n-2阶或者第n-1阶走到，则f(n) = f(n - 1) + f(n - 2)

搞清楚了边界条件和状态转移方程后编写程序：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;

int dp[45];

int get_steps(int n) {
    if (n == 1) return 1;
    else if (n == 2) return 2;
    if (dp[n]) return dp[n];
    return dp[n] = get_steps(n - 1) + get_steps(n - 2);
}

void solve(int n) {
    printf("%d", get_steps(n));
}

int main(int argc, char const *argv[])
{
    int n;
    scanf("%d", &n);
    solve(n);

    return 0;
}

注意程序使用了dp数组（动态规划）来优化内存。

运行结果： image.png