1458. 两个子序列的最大点积

发表于 分类于 阅读次数： Waline： 本文字数： 856 阅读时长 ≈ 3 分钟

考点

  • LCS

思路

一、问题回顾与建模视角

给定两个整数数组 \[ \text{nums1} = [a_1, a_2, \dots, a_{n_1}], \quad \text{nums2} = [b_1, b_2, \dots, b_{n_2}] \] 需要从两个数组中分别选择一个非空子序列，使得它们的点积最大： \[ \sum_{k=1}^{m} x_k \cdot y_k \] 其中 \((x_1,\dots,x_m)\) 是 nums1 的子序列， \((y_1,\dots,y_m)\) 是 nums2 的子序列，并且二者长度相同。

二、状态定义（State）

1. 状态含义

定义二维 DP 数组： \[ f[i][j] \] 表示：

只考虑 nums1 的前 \(i\) 个元素和 nums2 的前 \(j\) 个元素时，所能得到的「非空子序列对」的最大点积。

⚠️ 关键点：

  • 子序列 必须非空
  • 点积是“已经至少选过一对元素”的结果

这直接决定了 初始值不能是 0，否则会错误地允许“什么都不选”。

三、初始值设计（Initialization）

1. 为什么不能初始化为 0？

如果将 f 初始化为 0，那么在所有乘积为负数的情况下，DP 会倾向于“什么都不选”，返回 0，这是非法解（题目要求非空子序列）。

因此，必须将 f[i][j] 初始化为一个足够小的负数，表示“当前状态不可达”。

2. 代码中的做法

1
memset(f, 0xcf, sizeof(f));

在补码表示下，0xcf 对应一个极小的负数（近似 -1e9），安全且高效。

四、状态转移方程（Transition）

考虑 nums1[i-1] 和 nums2[j-1] 这两个元素是否被选入子序列。

情况 1：只选当前这一对，作为子序列的起点

\[ a_i \cdot b_j \]

这是最重要的一项，它保证了子序列至少包含一个元素对。

情况 2：在已有子序列的基础上，继续选这一对

\[ f[i-1][j-1] + a_i \cdot b_j \]

表示当前元素对接在之前的最优解之后。

情况 3：不选当前元素对

  • 不选 a_i： \[ f[i-1][j] \]

  • 不选 b_j： \[ f[i][j-1] \]

用于“跳过”某一侧的元素。

统一转移公式

\[ \boxed{ \begin{aligned} f[i][j] = \max \Big( & a_i \cdot b_j, \\ & f[i-1][j-1], \\ & f[i-1][j-1] + a_i \cdot b_j, \\ & f[i-1][j], \\ & f[i][j-1] \Big) \end{aligned} } \]

在代码中，逻辑被拆分为几次 max，但本质完全一致。

五、答案含义（Answer）

最终答案为： \[ \boxed{f[n_1][n_2]} \] 含义是：

在完整考虑两个数组后，能得到的最大非空子序列点积。

由于所有非法状态已被初始化为极小值，因此该结果一定对应一个合法、非空的子序列对。

六、时间与空间复杂度

  • 时间复杂度： \[ O(n_1 \times n_2) \]

  • 空间复杂度： \[ O(n_1 \times n_2) \]

在本题约束（\(n \le 500\)）下完全可接受。

七、AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    static const int maxn = 5e2 + 5;

    int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
        int f[maxn][maxn];
        int n1 = nums1.size(), n2 = nums2.size();

        // 初始化为极小值，表示“尚未形成非空子序列”
        memset(f, 0xcf, sizeof(f));

        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++j) {

                // 情况 1：仅选择 nums1[i-1] 和 nums2[j-1] 作为起点
                f[i][j] = nums1[i - 1] * nums2[j - 1];

                // 情况 2：在已有子序列后追加这一对
                f[i][j] = max(
                    f[i][j],
                    max(
                        f[i - 1][j - 1],  // 什么都不接，保留旧解
                        f[i - 1][j - 1] + nums1[i - 1] * nums2[j - 1]
                    )
                );

                // 情况 3：跳过某一侧元素
                f[i][j] = max(
                    f[i][j],
                    max(f[i - 1][j], f[i][j - 1])
                );
            }
        }

        // 最终答案
        return f[n1][n2];
    }
};