602金银珠宝的数值

问题描述

在一个神秘的竞技场中，勇敢的探险者小青拥有两个宝箱：一个宝箱里装满了 n 个金银珠宝的数值，另一个则是一个包含 m 个神秘符文的序列。小青面临着一个挑战：在接下来的 m 轮中，他必须在这两者之间做出明智的选择，以获得最高的财富。

在每一轮（第 i 轮）中，小青可以选择从宝箱的最上面或最下面取出一个珠宝 x。然后，他会将这个珠宝的价值乘以对应的符文 c[i]，并把结果累加到他的总财富中。被取出的珠宝将从宝箱中消失，接着小青会继续下一轮操作，直到完成 m 轮。

你的任务是帮助小青计算，在完成 m 轮挑战后，他可以获得的最高财富是多少。

输入：

• stones：宝箱中 n 个金银珠宝的数值
• c：m 个神秘符文

约束条件：

• 时间限制：3 秒
• 1 ≤ m ≤ n ≤ 2000
• -1000 ≤ stones[i], c[i] ≤ 1000

解题思路

这道题目可以通过动态规划和记忆化搜索来解决。小青在每一轮可以选择从宝箱的最上面或最下面取出一个珠宝，并将其价值乘以对应的符文，累加到总财富中。目标是最大化总财富。

使用递归加缓存（memoization）的方式来避免重复计算。定义一个函数 dfs(i, j)，表示在当前选择了 前i 个左端元素和 后j 个右端元素后的最大财富。

代码实现

from typing import List
from functools import cache
from sys import setrecursionlimit
setrecursionlimit(4010)

def solution(stones: List[int], c: List[int]) -> int:
    n, m = len(stones), len(c)
    @cache
    def dfs(i, j):
        if n - (j - i + 1) >= m:
            return 0
        return max(dfs(i + 1, j) + stones[i] * c[n - (j - i + 1)], dfs(i, j - 1) + stones[j] * c[n - (j - i + 1)])
    return dfs(0, n - 1)

if __name__ == '__main__':
    print(solution(stones=[-3, 4, 5], c=[2, -1, 3]) == 25)
    print(solution(stones=[6, -7, 1], c=[4, -3]) == 45)
    print(solution(stones=[3, 5, -2, 9], c=[1, 3, -5]) == 40)