🧗‍♂️适合初学者的指南 'Max Dot Product of Two Subsequences' – LeetCode 1458 (C++, Python, JavaScript)

Source: Dev.to

问题概述

给定：

• 两个整数数组，nums1 和 nums2。

你的目标：

• 找到两个数组中长度相同的非空子序列之间可能的最大点积。

直觉

这个问题的核心在于 动态规划。由于我们要寻找子序列，在每一步都要决定是把当前数字的乘积加入还是跳过它，以便以后找到更好的配对。

我们构建一个二维网格，其中 dp[i][j] 表示使用第一个数组从开头到索引 i 的元素以及第二个数组从开头到索引 j 的元素时能够得到的最大点积。

对于每一对索引 (i, j)，我们有三种选择：

1. 开始一个新的乘积或在之前的基础上扩展 —— 计算 A[i] * B[j]。如果之前的最佳结果 dp[i‑1][j‑1] 为正，则把它加到当前乘积上。
2. 跳过第一个数组的当前元素 —— 继承 dp[i‑1][j]。
3. 跳过第二个数组的当前元素 —— 继承 dp[i][j‑1]。

通过考虑这些选项，网格会逐步填充出可能的最大值，最终答案出现在右下角的单元格中。

代码块

C++

class Solution {
public:
    int maxDotProduct(vector& A, vector& B) {
        int n = A.size(), m = B.size();
        vector> dp(n, vector(m));

        for (int i = 0; i  0 && j > 0) {
                    dp[i][j] += max(dp[i - 1][j - 1], 0);
                }

                // Choice 2: Skip current element from A
                if (i > 0) {
                    dp[i][j] = max(dp[i][j], dp[i - 1][j]);
                }

                // Choice 3: Skip current element from B
                if (j > 0) {
                    dp[i][j] = max(dp[i][j], dp[i][j - 1]);
                }
            }
        }
        return dp[n - 1][m - 1];
    }
};

Python

class Solution:
    def maxDotProduct(self, A: List[int], B: List[int]) -> int:
        n, m = len(A), len(B)
        dp = [[0] * m for _ in range(n)]

        for i in range(n):
            for j in range(m):
                current_product = A[i] * B[j]

                if i > 0 and j > 0:
                    dp[i][j] = current_product + max(dp[i - 1][j - 1], 0)
                else:
                    dp[i][j] = current_product

                if i > 0:
                    dp[i][j] = max(dp[i][j], dp[i - 1][j])
                if j > 0:
                    dp[i][j] = max(dp[i][j], dp[i][j - 1])

        return dp[n - 1][m - 1]

JavaScript

/**
 * @param {number[]} A
 * @param {number[]} B
 * @return {number}
 */
var maxDotProduct = function (A, B) {
    const n = A.length;
    const m = B.length;
    const dp = Array.from({ length: n }, () => Array(m).fill(0));

    for (let i = 0; i  0 && j > 0) {
                dp[i][j] = currentProduct + Math.max(dp[i - 1][j - 1], 0);
            } else {
                dp[i][j] = currentProduct;
            }

            if (i > 0) {
                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
            }
            if (j > 0) {
                dp[i][j] = Math.max(dp[i][j], dp[i][j - 1]);
            }
        }
    }

    return dp[n - 1][m - 1];
};

关键要点

• 子序列 vs. 子数组: 子序列的元素不必是连续的，这就是我们可以使用 dp[i‑1][j] 和 dp[i][j‑1] “跳过”元素的原因。
• 动态规划的威力: 将中间结果存储在表格中，可将指数时间问题转化为可管理的二次时间问题。
• 处理负数: 表达式 max(dp[i‑1][j‑1], 0) 决定是使用之前的子序列来提升当前乘积，还是重新开始。

最终思考

这个问题展示了动态规划如何高效地探索大规模搜索空间。类似的技术被用于推荐系统（将用户兴趣与产品标签匹配）和生物信息学（比较 DNA 序列）。掌握这种模式能够在涉及大规模数据匹配的技术面试中提供强大的优势。