题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是对两个数组可以选非空子序列做点积，求其最大值。

思路分享

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        # 空间优化
        m, n = len(nums1), len(nums2)
        f = [-inf]*(n+1)
        # f[0] = 0
        for i in range(m):
            pre = f[0]
            for j in range(n):
                tmp = f[j+1]
                f[j+1] = max(f[j+1], f[j], pre+nums1[i]*nums2[j], nums1[i]*nums2[j])
                pre = tmp
        ans = f[n]
        # print(f)
        return ans
        # 递推
        # f[i][j][flag] = max(f[i-1][j][flag], f[i][j-1][flag], f[i-1][j-1][True]+nums1[i]*nums2[j])
        m, n = len(nums1), len(nums2)
        f = [[-inf]*(n+1) for _ in range(m+1)]
        f[0][0] = 0
        for i in range(m):
            for j in range(n):
                f[i+1][j+1] = max(f[i][j+1], f[i+1][j], f[i][j]+nums1[i]*nums2[j], nums1[i]*nums2[j])
        ans = f[m][n]
        # print(f)
        return ans
        # 记忆化搜索，对于两数组的前 i 和 前 j 项所得的最大点积
        @cache
        def dfs(i:int, j:int)->int:
            if i < 0 or j < 0:
                return 0 if (i < 0 and j < 0) else -inf
            return max(dfs(i-1, j), dfs(i, j-1), dfs(i-1, j-1)+nums1[i]*nums2[j], nums1[i]*nums2[j])
        return dfs(len(nums1)-1, len(nums2)-1)