戳气球

戳气球

有 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 =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167

暴力递归：

• 1 为了方便主要逻辑计算，现在nums数组的开头和结尾插入1.
• 2 计算完i之后，就将该数字跳过。

class Solution {
public:
    unordered_map<string, int> my_map;
    int traversal(vector<int>& nums){
        int n = nums.size();
        string path = "";
        for(auto num:nums) path += to_string(num);
        if (my_map.count(path)) return my_map[path];
        int result = 0;
        for(int i=1; i<n-1; i++){
            int temp = nums[i];
            int prod = nums[i-1] * nums[i] * nums[i+1];
            nums.erase(nums.begin()+i);
            result = max(result, prod + traversal(nums));
            nums.insert(nums.begin()+i, temp);
        }
        my_map[path] = result;
        return result;
    }

    int maxCoins(vector<int>& nums) {
        nums.insert(nums.begin(), 1);
        nums.insert(nums.begin()+nums.size(), 1);
        return traversal(nums);
    }
};