日拱一卒（19）——leetcode学习记录：两个子序列的最大点积

一、题目

给你两个数组 nums1 和 nums2 。

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

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

二、思路

遇事不决就递归，左脚踩右脚是升天最好的方式。

首先，这道题常规思路找不到解决办法。那么这里我们可以知道nums1和nums2只有一个数的时候，最大内积就是两个元素之积。初值已经解决，那么下一步则是递推关系，f[i][j]是nums1前i个元素的子序列和nums2前j个元素的子序列的子序列最大点积，将f[i][j]转换为前面的历史计算结果，即可找到递推关系。当nums1[i]和nums2[j]组成点积时，f[i][j] = max(f[i-1][j-1],f[i-1]f[j-1]+xij,xij)，不组成点积时,f[i][j] = max(f[i-1][j],f[i][j-1])，取两者最大值即可。

三、题解

class Solution:

    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:

        m,n = len(nums1),len(nums2)

        f = [[0]*n for _ in range(m)]

        for i in range(m):

            for j in range(n):

                xij = nums1[i]*nums2[j]

                f[i][j] = xij

                if i > 0:

                    f[i][j] = max(f[i][j],f[i-1][j])

                if j > 0:

                    f[i][j] = max(f[i][j],f[i][j-1])

                if i > 0 and j > 0:

                    f[i][j] = max(f[i][j],f[i-1][j-1]+xij)

        return f[m-1][n-1]