华为OD机考双机位C卷 - 构造数列 （Java Python JS GO C++ C）

# 构造数列

2026华为OD机试双机位C卷 - 华为OD上机考试双机位C卷

华为OD机试双机位C卷真题目录点击查看: 【全网首发】2026华为OD机位C卷 机考真题题库含考点说明以及在线OJ（OD上机考试双机位C卷）

题目描述

小明在做构造数列的题目，题目要求数列中第一个数为n，且数列后面的每一个数字都不能大于前一个数字的一半，数列的元素都是正整数，请问在给定n的情况下，最多能构造多少合法且不同的数列？

输入描述

输入一个n

备注

1 <= n< 10000

输出描述

输出可以构造的序列个数

示例1

输入

7

输出

6

说明

可以构成 [7], [7,3],[7,2],[7,1],[7,3,1],[7,2,1]

示例2

输入

5

输出

4

说明

可以构成 [5],[5,2],[5,1],[5,2,1]

解题思路

这个问题是要计算以给定数字n开头的所有可能序列数量，其中序列的每个后续数字不能大于前一个数字的一半。

核心思想：

1. 动态规划与记忆化搜索：使用自顶向下的动态规划方法，通过记忆化搜索避免重复计算相同的子问题。
2. 状态定义：countSequences(cur, memo)表示以数字cur开头的所有可能序列数量。
3. 递推关系：
   • 基本情况：每个数字至少能形成一个序列（即只包含自身）
   • 对于cur，我们尝试所有可能的下一个值i（1 ≤ i ≤ cur/2）
   • 递归计算以i开头的所有序列数量，并将这些数量累加
4. 记忆化：使用memo数组存储已计算的结果，避免重复计算。

时间复杂度分析：

• 没有记忆化的情况下，时间复杂度会是指数级的O(2^n)
• 使用记忆化后，每个状态只计算一次，总状态数为O(n)，每个状态的计算时间为O(n)，因此总时间复杂度为O(n²)