#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    int A[21];  // n 最大是 20，因此开个大小为 21 的数组即可（从 A[1] 开始）

    A[1] = 0;
    if (n >= 2) A[2] = 1;
    if (n >= 3) A[3] = 1;

    //用数组替代递归
    for (int i = 4; i <= n; i++) {
        A[i] = A[i - 3] + 2 * A[i - 2] + A[i - 1];
    }

    cout << A[n] << endl;
    return 0;
}

递归写法（你最开始的版本）：

cpp复制编辑int res(int n){
    if(n==1) return 0;
    if(n==2 || n==3) return 1;
    return res(n-3) + 2*res(n-2) + res(n-1);
}

看似很简洁，但有一个致命缺点：它会重复计算大量相同子问题！

🔍 举个例子：算 res(6) 时你会发生什么？

  • res(6) = res(3) + 2×res(4) + res(5)
  • 但要算 res(5) 又要算 res(3)、res(2)、res(4)
  • 然后又要算 res(3) ……重复算！

所以递归树会爆炸一样增长，大量重复计算导致效率低下！

⏱ 时间复杂度

  • 原始递归是指数级的：O(3^n)
  • 用数组存中间值，只需顺序扫一遍，变成线性复杂度 O(n)！

💡 再回答：怎么想到用数组？

你只要遇到这种模式：

“一个值依赖前几个值，而且每个值只用一次”，就该想到：用数组来存结果，避免重复计算，这是所谓的“记忆化”或“动态规划（DP）思想）”。

🚀 实用判断标准：什么时候该用数组（动态规划）

如果你看到：

  1. 递归公式（比如 A[n] = A[n-1] + ...）
  2. 会重复算同一个值（比如 res(4) 在多处出现）
  3. 题目给出的 n 比较大（比如 n ≤ 10^5）

就几乎可以确定：

✅ “用数组存中间值，别重复算了！”

✅ 数组写法回顾：

cpp复制编辑int A[21];
A[1] = 0;
A[2] = 1;
A[3] = 1;
for (int i = 4; i <= n; i++) {
    A[i] = A[i - 3] + 2 * A[i - 2] + A[i - 1];
}

这个写法每个值只算一次，总共 n 次循环，每次计算都非常快（只是加法和乘法），效率就是最优的。