区间动态规划例题：最长等差数列问题

字数 2298 2025-11-01 15:29:05

区间动态规划例题：最长等差数列问题

题目描述

给定一个整数数组 nums，返回数组中最长等差数列子序列的长度。等差数列子序列是指一个序列，其中任意相邻两个元素的差值相同。例如，对于数组 [3, 6, 9, 12]，其最长等差数列子序列就是它本身，长度为 4。

解题过程

问题分析
我们需要找到一个最长的子序列（注意：子序列不要求连续，但顺序必须与原数组相同），使得这个子序列是一个等差数列。例如，对于数组 [9, 4, 7, 2, 10]，最长等差数列是 [4, 7, 10] 或者 [9, 7, 5]（如果数组中有5的话），长度为 3。
动态规划状态定义
这是一个经典的区间动态规划问题。关键在于，当我们考虑一个等差数列时，仅仅知道以某个位置 i 结尾的最长长度是不够的，因为我们需要知道公差信息才能进行状态转移。
一个巧妙的定义是：
dp[i][d] 表示以数组下标 i 的元素结尾，且公差为 d 的最长等差数列的长度。
但是，公差 d 可能非常大，直接作为一个维度（数组索引）会使得空间复杂度过高。
状态定义的优化
我们可以利用哈希表来避免直接声明一个巨大的二维数组。具体来说，我们可以使用一个数组（或列表）dp，其中 dp[i] 本身是一个哈希表（比如 Python 中的 defaultdict 或 Java 中的 Map）。这个哈希表的键（key）是公差 d，值（value）是以 nums[i] 结尾、公差为 d 的等差数列长度。

即：
dp[i] 是一个映射（字典），对于每个可能的公差 d，dp[i].get(d) 存储了相应的长度。
状态转移方程
我们如何填充 dp[i] 呢？
对于当前位置 i，我们遍历它之前的所有位置 j (0 <= j < i)。
计算 i 和 j 两个位置元素的差值，也就是候选的公差：d = nums[i] - nums[j]。
现在，以 i 结尾、公差为 d 的等差数列，可以由以 j 结尾、公差为 d 的等差数列接上 nums[i] 而来。
因此，状态转移方程为：
dp[i][d] = dp[j].get(d, 1) + 1
这里 dp[j].get(d, 1) 的意思是：查看在 dp[j] 这个哈希表中，键为 d 的值是多少。如果存在（说明之前已经有过以 nums[j] 结尾、公差为 d 的序列），那么我们就用这个长度加 1。如果不存在（说明这是第一次出现以 nums[i] 和 nums[j] 构成的公差为 d 的序列），那么长度就应该是 2（即 nums[j] 和 nums[i] 这两个数），而 dp[j].get(d, 1) 会返回默认值 1，加 1 后正好是 2。

在每次更新 dp[i][d] 的同时，我们用一个变量 max_len 来记录全局遇到的最大长度。
初始化
对于数组中的每个位置 i，至少可以和自己构成一个长度为 1 的等差数列（公差任意，但通常我们只关心长度大于1的序列，所以长度为1的情况在状态转移中通过默认值1已经隐含处理了）。我们可以将每个 dp[i] 初始化为一个空的哈希表。全局最大值 max_len 初始化为 1（因为最短的等差数列长度至少为1）。
遍历顺序
我们需要从左到右遍历数组，对于每个 i，再遍历所有它左边的 j。这保证了当我们计算 dp[i] 时，所有 dp[j] (j < i) 都已经被计算过了。
复杂度分析
- 时间复杂度： O(n²)，其中 n 是数组的长度。因为我们需要两层循环来遍历所有 (i, j) 组合。
- 空间复杂度： O(n²)，在最坏情况下（例如数组元素都相同，公差为0），每个 dp[i] 可能只存储一个键值对，但总的空间消耗仍然是 O(n²) 级别，因为总共有 n 个哈希表，每个哈希表在最坏情况下可能存储 O(n) 个不同的公差（当数字分布稀疏时）。
举例说明
以 nums = [3, 6, 9, 12] 为例：
- i=0: dp[0] 是一个空字典。max_len = 1。
- i=1:
  - j=0: d = 6 - 3 = 3。dp[1][3] = dp[0].get(3, 1) + 1 = 1 + 1 = 2。max_len = max(1, 2) = 2。
- i=2:
  - j=0: d = 9 - 3 = 6。dp[2][6] = 1 + 1 = 2。
  - j=1: d = 9 - 6 = 3。dp[2][3] = dp[1].get(3, 1) + 1 = 2 + 1 = 3。max_len = max(2, 3) = 3。
- i=3:
  - j=0: d = 12 - 3 = 9。dp[3][9] = 2。
  - j=1: d = 12 - 6 = 6。dp[3][6] = dp[2].get(6, 1) + 1 = 2 + 1 = 3。
  - j=2: d = 12 - 9 = 3。dp[3][3] = dp[2].get(3, 1) + 1 = 3 + 1 = 4。max_len = max(3, 4) = 4。
    最终结果为 4。

总结
这道题的核心在于巧妙地使用“末尾元素索引 + 公差”作为状态，并且利用哈希表来灵活地存储不同公差对应的序列长度，从而高效地解决了问题。

区间动态规划例题：最长等差数列问题题目描述给定一个整数数组 nums，返回数组中最长等差数列子序列的长度。等差数列子序列是指一个序列，其中任意相邻两个元素的差值相同。例如，对于数组 [ 3, 6, 9, 12 ]，其最长等差数列子序列就是它本身，长度为 4。解题过程问题分析我们需要找到一个最长的子序列（注意：子序列不要求连续，但顺序必须与原数组相同），使得这个子序列是一个等差数列。例如，对于数组 [ 9, 4, 7, 2, 10]，最长等差数列是 [ 4, 7, 10] 或者 [ 9, 7, 5 ]（如果数组中有5的话），长度为 3。动态规划状态定义这是一个经典的区间动态规划问题。关键在于，当我们考虑一个等差数列时，仅仅知道以某个位置 i 结尾的最长长度是不够的，因为我们需要知道公差信息才能进行状态转移。一个巧妙的定义是： dp[i][d] 表示以数组下标 i 的元素结尾，且公差为 d 的最长等差数列的长度。但是，公差 d 可能非常大，直接作为一个维度（数组索引）会使得空间复杂度过高。状态定义的优化我们可以利用哈希表来避免直接声明一个巨大的二维数组。具体来说，我们可以使用一个数组（或列表） dp ，其中 dp[i] 本身是一个哈希表（比如 Python 中的 defaultdict 或 Java 中的 Map ）。这个哈希表的键（key）是公差 d ，值（value）是以 nums[i] 结尾、公差为 d 的等差数列长度。即： dp[i] 是一个映射（字典），对于每个可能的公差 d ， dp[i].get(d) 存储了相应的长度。状态转移方程我们如何填充 dp[i] 呢？对于当前位置 i ，我们遍历它之前的所有位置 j (0 <= j < i)。计算 i 和 j 两个位置元素的差值，也就是候选的公差： d = nums[i] - nums[j] 。现在，以 i 结尾、公差为 d 的等差数列，可以由以 j 结尾、公差为 d 的等差数列接上 nums[i] 而来。因此，状态转移方程为： dp[i][d] = dp[j].get(d, 1) + 1 这里 dp[j].get(d, 1) 的意思是：查看在 dp[j] 这个哈希表中，键为 d 的值是多少。如果存在（说明之前已经有过以 nums[j] 结尾、公差为 d 的序列），那么我们就用这个长度加 1。如果不存在（说明这是第一次出现以 nums[i] 和 nums[j] 构成的公差为 d 的序列），那么长度就应该是 2（即 nums[j] 和 nums[i] 这两个数），而 dp[j].get(d, 1) 会返回默认值 1，加 1 后正好是 2。在每次更新 dp[i][d] 的同时，我们用一个变量 max_len 来记录全局遇到的最大长度。初始化对于数组中的每个位置 i ，至少可以和自己构成一个长度为 1 的等差数列（公差任意，但通常我们只关心长度大于1的序列，所以长度为1的情况在状态转移中通过默认值1已经隐含处理了）。我们可以将每个 dp[i] 初始化为一个空的哈希表。全局最大值 max_len 初始化为 1（因为最短的等差数列长度至少为1）。遍历顺序我们需要从左到右遍历数组，对于每个 i ，再遍历所有它左边的 j 。这保证了当我们计算 dp[i] 时，所有 dp[j] (j < i) 都已经被计算过了。复杂度分析时间复杂度： O(n²)，其中 n 是数组的长度。因为我们需要两层循环来遍历所有 (i, j) 组合。空间复杂度： O(n²)，在最坏情况下（例如数组元素都相同，公差为0），每个 dp[i] 可能只存储一个键值对，但总的空间消耗仍然是 O(n²) 级别，因为总共有 n 个哈希表，每个哈希表在最坏情况下可能存储 O(n) 个不同的公差（当数字分布稀疏时）。举例说明以 nums = [3, 6, 9, 12] 为例： i=0: dp[0] 是一个空字典。 max_len = 1 。 i=1: j=0: d = 6 - 3 = 3 。 dp[1][3] = dp[0].get(3, 1) + 1 = 1 + 1 = 2 。 max_len = max(1, 2) = 2 。 i=2: j=0: d = 9 - 3 = 6 。 dp[2][6] = 1 + 1 = 2 。 j=1: d = 9 - 6 = 3 。 dp[2][3] = dp[1].get(3, 1) + 1 = 2 + 1 = 3 。 max_len = max(2, 3) = 3 。 i=3: j=0: d = 12 - 3 = 9 。 dp[3][9] = 2 。 j=1: d = 12 - 6 = 6 。 dp[3][6] = dp[2].get(6, 1) + 1 = 2 + 1 = 3 。 j=2: d = 12 - 9 = 3 。 dp[3][3] = dp[2].get(3, 1) + 1 = 3 + 1 = 4 。 max_len = max(3, 4) = 4 。最终结果为 4。总结这道题的核心在于巧妙地使用“末尾元素索引 + 公差”作为状态，并且利用哈希表来灵活地存储不同公差对应的序列长度，从而高效地解决了问题。