第3篇

#include<iostream>

int choose[20];
int dfs(int m, int n)
{
    if (m == n) {
        bool flag = true;
        for (int i = 0; i + 1 < n; ++i) {
            if (choose[i] && choose[i+1]) {
                flag = false;
            }
        }
        if (flag) {
            return 1;
        }
        else {
            return 0;
        }
    }
    else {
        choose[m] = true;
        int pick = dfs(m+1, n);
        choose[m] = false;
        int drop = dfs(m+1, n);
        return pick + drop;
    }
}

int fib(int n)
{
    int f[21];
    f[0] = 1;
    f[1] = 2;
    for (int i = 2; i <= n; ++i) {
        f[i] = f[i-1] + f[i-2];
    }
    return f[n];
}

int main()
{
    int n;
    std::cin >> n;
    std::cout << dfs(0, n) << " ";
    std::cout << fib(n) << "\n";
}

dfs 函数采用的算法思想是（ ）。

{{ select(1) }}

• 迭代
• 分治
• 枚举
• 动态规划