1458. 两个子序列的最大点积（Rating 1823）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

1458. 两个子序列的最大点积

Rating 1823

思路

动态规划

思考：对于nums1[i]和nums2[j]，如果i, j之前的序列最大点积和已求出，如果求当前序列的最大点积和？

设dp[i][j]表示nums1[0:i]和nums2[0:j]的非空序列的最大点积和

那么状态转移方程：

1. 当同时选择使用nums1[i]和nums2[j]时
   1. 当采用之前序列的点积和时，dp[i][j] = dp[i-1][j-1] + nums1[i] * nums2[j]
   2. （这点很容易被忽略掉）当不采用之前序列的点积和时，dp[i][j] = nums1[i] * nums2[j]
2. 当不选择使用nums1[i]时，dp[i][j] = dp[i - 1][j]
3. 当不选择使用nums2[j]时，dp[i][j] = dp[i][j - 1]
4. 当不选择使用nums1[i]和nums2[j]时，dp[i][j] = dp[i - 1][j - 1]

代码

class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        m, n = len(nums1), len(nums2)
        dp = [[0 for _ in range(n)] for _ in range(m)]
        dp[0][0] = nums1[0] * nums2[0]
        for i in range(1, m): # 处理边界情况
            dp[i][0] = max(dp[i - 1][0], nums1[i] * nums2[0])
        for j in range(1, n): # 处理边界情况
            dp[0][j] = max(dp[0][j - 1], nums1[0] * nums2[j])
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = max(
                    nums1[i] * nums2[j], 
                    dp[i - 1][j - 1] + nums1[i] * nums2[j], 
                    dp[i - 1][j], 
                    dp[i][j - 1]
                )
        return dp[-1][-1]