LeetCode-3290 最高乘法得分

Table of Contents

LeetCode-3290 最高乘法得分 #

Solution 1 #

用 $dp[i][j]$ 表示 $a[0:i + 1]$ 和 $b[:j+1]$ 的最大乘法得分, 每次考虑当前是否匹配即可.

代码如下:

class Solution:
    def maxScore(self, a: List[int], b: List[int]) -> int:
        dp = [[-inf for _ in b] for _ in range(4)]
        for j, x in enumerate(b):
            for i in range(4):
                dp[i][j] = max(-inf if j <= i else dp[i][j - 1], a[i] * x + (dp[i - 1][j - 1] if i > 0 else 0))
        return dp[3][-1]