小红的数列

[题目链接](https://www.nowcoder.com/practice/e13cc81840644eef9c0a6694ae7e5ad3)

思路

本题给出数列的定义：，，从第三项起满足递推关系：

$$

要求输出前 项。

递推（动态规划）

由于 且 （当 时均成立），所以从小到大依次计算即可，每个 所依赖的项都已经被计算过了。

直接开一个数组，从 递推到 ，每步 ，总共 。

样例验证

时：
1 — — 1
2 — — 2
3 1 2
4 1 2
5 1 3

输出 1 2 3 3 4，与样例一致。

代码

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<long long> a(n + 1);
    if (n >= 1) a[1] = 1;
    if (n >= 2) a[2] = 2;
    for (int i = 3; i <= n; i++) {
        a[i] = a[i / 3] + a[2 * i / 3];
    }
    for (int i = 1; i <= n; i++) {
        if (i > 1) cout << " ";
        cout << a[i];
    }
    cout << 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();
        long[] a = new long[n + 1];
        if (n >= 1) a[1] = 1;
        if (n >= 2) a[2] = 2;
        for (int i = 3; i <= n; i++) {
            a[i] = a[i / 3] + a[2 * i / 3];
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            if (i > 1) sb.append(' ');
            sb.append(a[i]);
        }
        System.out.println(sb);
    }
}

复杂度分析

  • 时间复杂度：，从 到 各计算一次，每次 。
  • 空间复杂度：，存储数列的前 项。