题解 | #牛牛学数列6#

题目链接

牛牛学数列6

题目描述

定义一个数列 A 如下：

A(1) = 0
A(2) = 1
A(3) = 1
A(n) = A(n-3) + 2*A(n-2) + A(n-1) (当 n ≥ 4)

给定一个正整数 n，求 A(n) 的值。

输入描述: 输入一个整数 n (1 ≤ n ≤ 30)。

输出描述: 输出一个整数，表示 A(n) 的值。

解题思路

本题给出了一个自定义的递推数列，其形式比斐波那契数列稍微复杂，当前项 A(n) 由它前面的三项 A(n-1), A(n-2), A(n-3) 共同决定。

由于 n 的范围很小（最大为30），解决这个问题的最直接和标准的方法是使用动态规划 (Dynamic Programming)。

算法步骤（DP数组法）：

处理特殊（基础）情况: 题目直接给出了前三项的值。如果输入的 n 是 1, 2, 或 3，我们可以直接返回对应的值 0, 1, 1。
创建 DP 数组: 创建一个大小为 n+1 的数组 dp，其中 dp[i] 用来存储数列第 i 项 A(i) 的值。
初始化 DP 数组: 根据题目定义，填充数组的前几个值：
- dp[1] = 0
- dp[2] = 1
- dp[3] = 1
循环递推: 从第 4 项开始，我们可以通过循环来计算后续的每一项。设置一个从 i = 4 到 n 的循环。在循环内部，应用题目给出的递推公式： dp[i] = dp[i-3] + 2*dp[i-2] + dp[i-1]
返回结果: 循环结束后，dp[n] 中存储的就是我们想要的最终结果 A(n)。

这种自底向上的计算方法避免了递归中可能出现的重复计算，效率很高，非常适合处理这类问题。

代码

c++
java
python

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    
    if (n == 1) {
        cout << 0 << endl;
        return 0;
    }
    if (n == 2 || n == 3) {
        cout << 1 << endl;
        return 0;
    }
    
    // 创建DP数组
    vector<long long> dp(n + 1);
    
    // 初始化基础项
    dp[1] = 0;
    dp[2] = 1;
    dp[3] = 1;
    
    // 循环递推
    for (int i = 4; i <= n; ++i) {
        dp[i] = dp[i - 3] + 2 * dp[i - 2] + dp[i - 1];
    }
    
    cout << dp[n] << endl;
    
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        if (n == 1) {
            System.out.println(0);
            return;
        }
        if (n == 2 || n == 3) {
            System.out.println(1);
            return;
        }

        // 创建DP数组，使用long防止溢出
        long[] dp = new long[n + 1];

        // 初始化基础项
        dp[1] = 0;
        dp[2] = 1;
        dp[3] = 1;

        // 循环递推
        for (int i = 4; i <= n; i++) {
            dp[i] = dp[i - 3] + 2 * dp[i - 2] + dp[i - 1];
        }

        System.out.println(dp[n]);
    }
}

n = int(input())

if n == 1:
    print(0)
elif n == 2 or n == 3:
    print(1)
else:
    # 创建DP列表
    dp = [0] * (n + 1)
    
    # 初始化基础项
    dp[1] = 0
    dp[2] = 1
    dp[3] = 1
    
    # 循环递推
    for i in range(4, n + 1):
        dp[i] = dp[i - 3] + 2 * dp[i - 2] + dp[i - 1]
        
    print(dp[n])

算法及复杂度

算法：动态规划。
时间复杂度： $\mathcal{O}(n)$ 。因为我们执行一个从 4 到 n 的线性循环。
空间复杂度： $\mathcal{O}(n)$ 。因为我们使用了一个大小与 n 成正比的数组来存储所有中间计算结果。