1458. Max Dot Product of Two Subsequences

https://leetcode.com/problems/max-dot-product-of-two-subsequences

Python

Bottom-Up DP

from functools import cache
from math import inf


class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        n, m = len(nums1), len(nums2)

        @cache
        def dp(i, j):
            if i == n or j == m:
                return -inf
            
            return max(
                nums1[i] * nums2[j] + max(dp(i+1, j+1), 0),
                dp(i+1, j),
                dp(i, j+1)
            )
        return dp(0, 0)

Top Down DP

class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        n, m = len(nums1), len(nums2)

        dp = [[-inf] * (m+1) for _ in range(n+1)]

        for i in range(n + 1):
            for j in range(m + 1):
                if i == 0 or j == 0:
                    dp[i][j] = float('-inf') 
                    continue
                    
                dp[i][j] = max(
                    nums1[i - 1] * nums2[j - 1] + max(dp[i - 1][j - 1], 0),  
                    dp[i - 1][j],  
                    dp[i][j - 1],  
                )

        return dp[n][m]