动态规划 Leetcode 1458 Max Dot Product of Two Subsequences（两个子序列的最大点积）

题目

给你两个数组 nums1 和 nums2 。请你返回 nums1 和 nums2 中两个长度相同的 非空 子序列的最大点积。

数组的非空子序列是通过删除原数组中某些元素（可能一个也不删除）后剩余数字组成的序列，但不能改变数字间相对顺序。比方说，[2,3,5] 是 [1,2,3,4,5] 的一个子序列而 [1,5,3] 不是。

链接（中文版）：https://leetcode-cn.com/problems/max-dot-product-of-two-subsequences/

链接（英文版）：https://leetcode.com/problems/max-dot-product-of-two-subsequences/

分析

如下两个数组，当求最优解时（记为M[4][3]，这里4和3是数组的脚标+1），考虑最优的两个子序列是否包含5和-6。

如果都不包含，则此时备选答案是蓝色数组的最优解M[3][2]（根据动态规划，这个值已经求得）。

如果都包含，则此时备选答案是M[3][2]+(5*-6)。

如果只包含5，则此时备选答案是M[4][2]（根据动态规划，这个值已经求得）。注意：M[4][2]里到底有没有使用5，我们不需要关心。

如果只包含-6，则此时备选答案是M[3][3]（根据动态规划，这个值已经求得）。注意：M[3][3]里到底有没有使用-6，我们不需要关心。

此时已经有了四个备选答案，选出最大的，就是M[4][3]了。但还有一种情况，即M[3][2]、M[4][2]和M[3][3]全都小于0，则此时最优解可能是5*-6。因此最终M[4][3]=max(四个备选答案，5*-6)。

最后再考虑一个细节：M[3][2]其实是M[4][2]和M[3][3]的子集，因此后两个结果必定大于等于M[3][2]。于是我们只需要对比后三个备选答案以及5*-6即可。

求解流程

对上述例子：nums1 = [2,1,-2,5], nums2 = [3,0,-6]

用如下矩阵M存储答案（为方便计算，M的宽高分别为两个数组长度+1，即5行4列，黑数字是M的行号列号）；由于存在负数，将M初始化为最小负整数（这里用减号-代替）。

首先计算M[1][j]，j从1到3，即计算数组[2]和 [3]的最优解、数组[2]和 [3, 0]的最优解以及数组[2]和 [3, 0, -6]的最优解。口算即可知道答案都是6。

然后计算M[2][j]，j从1到3，即计算数组[2, 1]和 [3]的最优解、数组[2, 1]和 [3, 0]的最优解以及数组[2, 1]和 [3, 0, -6]的最优解。当计算M[2][3]时，M[2][3]=max(M[1][2]+nums1[1]*nums2[2], M[1][3], M[2][2], nums1[1]*nums2[2])=max(6+(-6), 6, 6, -6)=6。

最终结果如下，返回最右下角的数即可。

代码

class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        n1, n2 = len(nums1), len(nums2)
        M = [[-100000] * (n2 + 1)  for _ in range(n1 + 1)] #这里用-100000就能通过了，说明测试用例中没有比-100000更小的结果。

        for i in range(n1):
            for j in range(n2):
                M[i+1][j+1] = max(M[i][j]+nums1[i]*nums2[j], M[i][j+1], M[i+1][j], nums1[i]*nums2[j])
        return M[-1][-1]