题目描述

一个楼梯共有 n级台阶，每次可以走一级或者两级，请问从第 0级台阶走到第 n级台阶一共有多少种方案。

输入格式
共一行，包含一个整数 n

输出格式
共一行，包含一个整数，表示方案数。

数据范围
1≤n≤15

输入样例：
5
输出样例：
8

优化思路:dfs —> 记忆化搜索 —>递归(最简单的dp)

Ⅰ

#include<bits/stdc++.h>
using namespace std;

int dfs(int n)
{
    if(n == 1) return 1;
    else if(n == 2) return 2;
    else return dfs(n - 1) + dfs (n - 2);
}

int main()
{
    int n;
    cin>>n;
    cout<<dfs(n)<<endl;
    return 0;
}

Ⅱ

#include<bits/stdc++.h>
using namespace std;

const int N = 100;
int mem[N];

int dfs(int x)
{
    if(mem[x]) return mem[x];

    int sum = 0;
    if(x == 1) return 1;
    else if(x == 2) return 2;
    else sum = dfs(x - 1) + dfs(x - 2);

    mem[x] = sum;
    return sum;

}

int main()
{
    int x;
    cin>>x;
    cout<<dfs(x)<<endl;
    return 0;
}

Ⅲ

#include<bits/stdc++.h>
using namespace std;

const int N = 10010;

int f[N];

int main()
{
    int n;
    cin>>n;
    f[1] = 1;
    f[2] = 2;

    if(n == 1 || n == 2)
    {
        cout<<f[n]<<endl;
        return 0;
    }

    for(int i = 3; i <= n; i++)
    {
        f[i] = f[i - 1] + f[i - 2];
    }

    cout<<f[n]<<endl;

    return 0;
}

递归: 自顶向下; 递推: 自底向下(底为最小子问题的答案)

递推的初始值 = 递归的边界

递推的公式为: dfs向下递归的公式(dfs的状态转移方程)