困难 Leetcode 312. 戳气球 区间dp/记忆化搜索

描述

有 n 个气球，编号为0 到 n – 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i – 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i – 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i – 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。

求所能获得硬币的最大数量。

示例 1：
输入：nums = [3,1,5,8]
输出：167
解释：
nums = [3,1,5,8] –> [3,5,8] –> [3,8] –> [8] –> []
coins = 315 + 358 + 138 + 181 = 167

示例 2：
输入：nums = [1,5]
输出：10

思路

不要想先戳哪个，想最后戳的是哪个。
或者这个场景可以等效为逆序场景：向槽位中添加气球，添加一个就加一次分数。
想法过于精妙，看代码懂的都懂。

启发：一开始自己总想着进行某些数学证明，看来做编程题最好还是不要往这方向去钻

代码

不多说直接看懂

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        n=len(nums)
        self.nums = [1]+nums+[1]

        return self.dfs(1,n)
    
    @cache
    def dfs(self,i,j):
        if i>j:
            return 0
        return max( self.dfs(i,k-1)
                    +self.dfs(k+1,j)
                    +self.nums[i-1]*self.nums[k]*self.nums[j+1]
                    for k in range(i,j+1))