Q:How it guarantees that it is the answer to the subsequence of equal length, can’t it be the answer of the subsequence of unequal length?? A:All the values are accumulated by the product of a pair.

class Solution:
    def maxDotProduct(self, A: List[int], B: List[int]) -> int:
        """tc O(M*N) sc O(M*N)
        base case: dp[i][j] = A[i-1]* B[j-1]
        next step can be solution from previous row, previous col,  previous top left diognal cell's max val plus current A[i-1]* B[j-1]

        dp[i][j] : max product sum before A[0...i] and B[0...j]
        """
        dp = [[float('-inf')] * (len(B)+1) for _ in range(len(A)+1)]
        for i in range(1,len(A)+1):
            for j in range(1,len(B)+1):
                dp[i][j] = max(A[i-1]*B[j-1],A[i-1]*B[j-1] + dp[i-1][j-1], dp[i][j-1],dp[i-1][j])
        return dp[-1][-1]

space optimization

class Solution:
    def maxDotProduct(self, A: List[int], B: List[int]) -> int:
        """
        tc O(MN) sc O(min(M,N))
        """
        memo = [-10e7] * (len(B) + 1)
        for a in A:
            prev = -10e7
            for i, b in enumerate(B):
                prod = a * b
                prev, memo[i] = memo[i], max(memo[i], memo[i-1], prev + prod, prod)
        return return memo[-2] # answer is at memo[len(B)] but if we create len(B) +1  space, we can skip processing case when i == 0 since it will go to memo[-1]

Recursion solution

from functools import lru_cache
class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        @lru_cache(None)
        def helper(i, j):
            if i == 0 or j == 0: return -math.inf
            return max(helper(i - 1, j - 1), helper(i, j - 1), helper(i - 1, j),
                       max(helper(i - 1, j - 1), 0) + nums1[i - 1] * nums2[j - 1])
        return helper(len(nums1), len(nums2))