1. 问题背景与理解LeetCode 1458题两个子序列的最大点积是一道典型的动态规划应用题。题目要求我们找到两个数组nums1和nums2的非空子序列使得它们的点积最大化。这里的子序列指的是保持相对顺序但不一定连续的元素序列。点积的计算方式是两个序列对应位置元素乘积的和。例如对于子序列[a1,a2,a3]和[b1,b2,b3]它们的点积就是a1b1 a2b2 a3*b3。题目要求我们找到所有可能的子序列组合中点积最大的那个值。这个问题看似简单但隐藏着几个关键点子序列的长度可以不同吗不可以点积要求两个序列长度相同空子序列是否允许题目明确要求非空子序列的元素顺序是否可以改变不可以必须保持原数组中的相对顺序2. 动态规划思路解析2.1 状态定义对于这类序列匹配问题动态规划是首选方法。我们需要定义一个二维DP数组dp[i][j]表示nums1前i个元素和nums2前j个元素能形成的最大点积这里i和j的范围分别是0到len(nums1)和0到len(nums2)其中dp[0][0]表示两个空子序列的点积根据题意应该初始化为负无穷因为不允许空子序列2.2 状态转移方程状态转移需要考虑三种情况不使用nums1[i-1]和nums2[j-1]dp[i][j] dp[i-1][j-1]只使用nums1[i-1]和nums2[j-1]dp[i][j] nums1[i-1]*nums2[j-1]尝试将当前元素与之前的最大点积组合dp[i][j] dp[i-1][j-1] nums1[i-1]*nums2[j-1]此外还需要考虑dp[i][j] max(dp[i][j], dp[i-1][j]) // 忽略nums1的当前元素dp[i][j] max(dp[i][j], dp[i][j-1]) // 忽略nums2的当前元素2.3 初始化边界条件处理dp[0][0] -inf 不允许空子序列dp[i][0] -inf for i 0dp[0][j] -inf for j 03. 代码实现与优化3.1 基础实现def maxDotProduct(nums1, nums2): m, n len(nums1), len(nums2) dp [[-float(inf)] * (n 1) for _ in range(m 1)] for i in range(1, m 1): for j in range(1, n 1): curr nums1[i-1] * nums2[j-1] dp[i][j] max( curr, # 只取当前元素对 dp[i-1][j-1] curr, # 当前元素对加上之前的 dp[i-1][j], # 不取nums1的当前元素 dp[i][j-1] # 不取nums2的当前元素 ) return dp[m][n]3.2 空间优化注意到dp[i][j]只依赖于左边、上边和左上方的值可以将空间复杂度从O(mn)优化到O(n)def maxDotProduct(nums1, nums2): m, n len(nums1), len(nums2) prev [ -float(inf) ] * (n 1) for i in range(1, m 1): curr [ -float(inf) ] * (n 1) for j in range(1, n 1): product nums1[i-1] * nums2[j-1] curr[j] max( product, prev[j-1] product, prev[j], curr[j-1] ) prev curr return prev[n]4. 边界情况与测试用例4.1 典型测试用例# 用例1常规情况 nums1 [2,1,-2,5] nums2 [3,0,-6] # 最大点积是18 2*3 1*0 (-2)*(-6) # 用例2全正数 nums1 [3,5,8] nums2 [2,4,6] # 最大点积是5*6 8*6 78 # 用例3全负数 nums1 [-1,-2] nums2 [-3,-4] # 最大点积是(-1)*(-3) 34.2 特殊边界情况# 单元素数组 nums1 [5] nums2 [4] # 结果应为20 # 包含0的数组 nums1 [1,0,1] nums2 [0,1,0] # 有多种可能最大为1 # 所有组合都是负数 nums1 [-1,-2] nums2 [-3,-4] # 需要选择单个元素对结果为125. 算法复杂度分析时间复杂度O(mn)其中m和n分别是两个数组的长度。我们需要填充一个m×n的DP表格。空间复杂度基础实现O(mn)优化实现O(n)在实际LeetCode提交中Python版本的优化实现运行时间约为100-200ms内存消耗在14MB左右能够通过所有测试用例。6. 类似题目与扩展6.1 LeetCode类似题目1143.最长公共子序列1035.不相交的线72.编辑距离53.最大子数组和6.2 问题变种思考如果题目改为允许空子序列点积为0如何修改要求输出具体的子序列而不仅是最大点积值如果子序列长度可以不同补零对齐如何处理对于第一个变种只需要将dp[0][0]初始化为0即可。第二个变种需要额外维护路径信息。第三个变种会显著增加问题复杂度。7. 实际应用场景这种最大点积问题在实际中有多种应用自然语言处理中计算句子相似度图像识别中的特征匹配推荐系统中的用户-商品偏好匹配金融领域的投资组合优化理解这类动态规划问题有助于解决许多序列匹配和优化问题。掌握状态定义和转移方程的构建技巧是解决复杂动态规划问题的关键。