Leetcode題解 Python：Max Dot Product of Two Subsequences

給兩個陣列 nums1 和 nums2。回傳兩陣列中非空子序列(皆相同長度)的最大的點積(Dot Product)。

子序列可以是以原陣列刪除部分(也可以不刪)，但元素的相對順序不變。

dot product的運算：

假設從 nums1 跟 nums2 取出 A 序列 跟 B序列。

A1、A2、A3

B1、B2、B3

=> A1*B1 + A2*B2 + A3*B3 => value

我又沒在時限內做完contest，QQ。

這題使用 DP 的觀念，用 p1 p2 代表兩陣列的點乘位置並加上後續的最大值，同時也是規劃 DFS 的遞迴函數。

由於不能有空值，一定要有個兩位置相乘作為開頭。即 nums1[p1] * nums2[p2] 。

面對 DFS 的設計，要從底開始想，也就是到底的情形。即 nums1[len(nums1)-1] * nums2[len(nums2)-1]。因為不能為空串列，該位置只有 nums1[p1] * nums2[p2] 的可能。

DP[len(nums1)-1][len(nums2)-1] ==  nums1[len(nums1)-1] * nums2[len(nums2)-1]

往上回傳，上面會是 p1-1 或是 p2-1 的，這樣不是 p2 會被重複乘到，不然就是 p1 。有共用的情況下，應該要取最大的可能，自身點乘跟下一個(下方、右方)取最大值，然後決定當前位置的 DP 值。

重點來了，那要如何再取更多，也就是要變成多組的情況。

每一對 p1, p2 都是一個點乘，其左上一個 p1-1,  p2-1 。

對 p1-1,  p2-1 來說，除了乘積外，還要加上 DP[p1][p2]的值，也就是後面的最大可能，如果後方最大值小於零，則不加。

這樣就能用到多組，從多組中找出最大的數值。

 

整理一下順序。

先算出 nums1[p1] * nums2[p2] ，視狀況加上 DP[p1+1][p2+1] 的值，成為該位置的基礎值。

跟下方(共用一個)的取最大值，即 DP[p1][p2] = max(DP[p1][p2], DP[p1+1][p2], DP[p1][p2+1])。

Python

class Solution:
    def maxDotProduct(self, nums1, nums2) -> int:
        
        from functools import lru_cache
        n1, n2 = len(nums1), len(nums2)
        @lru_cache(None)
        def dfs(p1, p2):
            if p1 > n1-1 or p2 > n2-1:
                return 0
            ans = nums1[p1] * nums2[p2]
            if p1 < n1 - 1 and p2 < n2 - 1:
                ans += max(dfs(p1+1, p2+1), 0)
            if p1 < n1 - 1:
                ans = max(ans, dfs(p1+1, p2))
            if p2 < n2 - 1:
                ans = max(ans, dfs(p1, p2+1))
            return ans

        return dfs(0,0)