递归写法-裸递归

裸递归写法是纯粹的递归写法，这种写法的时间复杂度呈指数级增长。

#include <stdio.h> 
int solution(int n)
{
    if (n < 4)
    {
         return n == 1 ? 0 : 1;
    }
   
    return solution(n - 3) + 2 * solution(n - 2) + solution(n - 1);
}
int main() {
   
    int n = 0;
    scanf("%d", &n);
    printf("%d", solution(n));
    return 0;
}

​递归写法-含有备忘录

含有备忘录（散列表）的递归。

用定长数组 memo[] 实现缓存数组，键就是 n，查找/插入均为 O(1)。

#include <stdio.h>
#include <stdint.h>

#define MAX 20
#define INVALID -1

uint32_t memo[MAX + 1];

uint32_t solution(uint32_t n)
{
    if (n < 4)
    {
         return n == 1 ? 0 : 1;
    }

    if (memo[n] != INVALID)
    {
        return memo[n];         // 已经计算过，直接返回
    }

    memo[n] = solution(n - 3) + 2 * solution(n - 2) + solution(n - 1);
    return memo[n];
}
int main() {
    uint32_t n = 0;

    // 初始化备忘录
    for (int i = 0; i <= MAX; i++)
    {
        memo[i] = INVALID;
    }

    scanf("%u", &n);
    printf("%u", solution(n));
    return 0;
}

非递归写法-迭代

题目已说明这是数列题，那么可以用指针移动的思想进行迭代

#include <stdio.h>
#include <stdint.h>
uint32_t solution(uint32_t n)
{
    if (n < 4)
    {
        return n == 1 ? 0 : 1;
    }
  
    int cur = 0;    // 当前计算出的 An 值
    int a1 = 0, a2 = 1, a3 = 1; // a1 到 a3 类比于指针，初始分别指向数列的前 3 项
  
    for (uint32_t i = 4; i <= n; i++)
    {
        // 计算出当前 An 的值，即 Ai 的值（当 n = i 时，An 的值）
        // 此时的 cur 表示着 a4 指针
        cur = a1 + 2 * a2 + a3;

        // 指针移动
        a1 = a2;
        a2 = a3;
        a3 = cur;
    }
  
    return cur;
}
int main() {
    uint32_t n = 0;
  
    scanf("%u", &n);
    printf("%u", solution(n));
    return 0;
}