当前位置：首页 > article >正文

3290. 最高乘法得分

article 2024/9/21 8:10:29

在这里插入图片描述

心路历程：

1、第一次做周赛的题，第一眼发现和之前hot100里面有一道两个子序列的dp很像，写完之后发现又是像之前一样超时，大概97ac
2、看了灵神的题解，发现主要问题出在建模没建好，还是应该以选or不选去考虑递推
3、在dp中还是尽量少用循环去表示选哪个的方式

选or不选：

这道题最神奇的地方在于，如果下面这个递推的max顺序反过来就会超内存。感觉用递归解动态规划还是有一定的限制的其实。。。
而且下面这个解答的初始判断条件的顺序也不能变，第一感觉dp问题好像用递归性价比不是很高。

class Solution:
    def maxScore(self, a: List[int], b: List[int]) -> int:
        @cache
        def dp(i:int, j:int) -> int:  # 前i个a和前j个b组成的得分最大值
            if j < 0: return 0
            if i < 0: return -inf
            return max(dp(i-1, j), dp(i-1, j-1) + a[j] * b[i])
        return dp(len(b)-1, 3)

97 ac 解(超时)：选哪个：

class Solution:
    def maxScore(self, a: List[int], b: List[int]) -> int:
        # 
        n = len(b)
        @cache
        def dp(i, j):  # 前i个a和前j个b组成的得分最大值
            # print(i, j)
            if j < i: res= -float('inf')
            elif j == i: res= sum([a[k]*b[k] for k in range(i+1)])
            else:
                if i == 0: 
                    res = max([a[0]*eve for eve in b[:j+1]])
                else: # i != 0 and j > i; a[i]必选,选b[k], k \in [j, len()]
                    res = max([dp(i-1, k-1) + a[i] * b[k] for k in range(j+1)])
                    # res = max(dp(i-1, j), dp(i-1, j-1) + a[i]*b[j])
            # print(i, j, res)
            return res
        ans = dp(3, n-1)
        return ans

            # [3, 2] [2, -6, 4, -5] -> [3, 2, 5] [2, -6, 4, -5]