一、题目
给你两个数组 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]
