题目描述

有 n 个气球，每个气球上标有一个数字。每次戳破一个气球，你将获得 nums[left] * nums[i] * nums[right] 个硬币，其中 left 和 right 是相邻气球的索引（不存在则视为值为 1）。求能获得硬币的最大数量。关键思路是逆向思维：考虑最后被戳破的气球，使用区间 DP，令 dp[i][j] 表示戳破开区间 (i,j) 内所有气球能获得的最大硬币数。