LeetCode-312.戳气球、动态规划

有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。现在要求你戳破所有的气球。如果你戳破气球 i ，就可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。求所能获得硬币的最大数量。
来源：力扣（LeetCode）第312题

暴力穷举

①．回溯算法
对于求最值的问题，最直接的思路是进行暴力穷举，按照题目要求枚举所有情况，一般可以采用深度优先搜索 + 回溯的方法。
②．代码示例

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int res = 0;//保存结果
        int cursort = 0;//保存中间值
        dfs(nums,cursort,res);//深度优先搜索枚举所有可能
        return res;
    }
    void dfs(vector<int>& nums,int sort,int &res)
    {
        // 基线条件：没有气球剩余，直接返回结果
        if( nums.size() ==0 )
        {
            res = max(res,sort);
            return;
        }
        // 枚举当前的所有可能的选择
        for( int i = 0;i < nums.size();i++)
        {
            // 本次戳气球得到的硬币
            int temp_sort = nums[i];
            if( i-1 >=0 )
                temp_sort = temp_sort * nums[i-1];
            if( i+1 <= nums.size()-1)
                temp_sort = temp_sort * nums[i+1];
            //构建当前数组的副本，并删除 i 元素
            vector<int> temp_nums(nums);
            temp_nums.erase(temp_nums.begin()+i);//删掉 i 元素
            //选择结果带入下一步操作
            dfs( temp_nums,sort+temp_sort,res);
            // 回溯，恢复本次的选择
            // 操作的是当前的副本，所以没有操作
        }
    }
};

回溯算法比较简单直接，但是算法效率很低，时间复杂度是 n 的阶乘级别。

动态规划

①．题目分析
动态规划也是一种穷举的算法，但是动态规划是把一个问题转换成了较小规模的子问题，从而减少算法时间复杂度。
动态规划的关键是，子问题必须是独立的。在戳气球的过程中，只有当戳最后一个气球的时候，获得的硬币数量是明确的，并且和其他气球不相关。
根据题意，可以认为是首尾的两个气球是不能戳的，因为题目可以转换为求在一个开区间中戳破所有气球能得到的硬币的最大值。
要想使某个位置的气球是最后戳破的，那必须把以此位置为分界的两个子区间的气球先戳破，即把当前问题转换成了子问题。

②．定义状态
在原数组头尾分别添加一个新的元素，首尾两个位置的气球不能戳破；定义 dp[i][j] 是开区间 (i,j) 戳破所有气球得到的最大值。i 和 j 是所有子区间的边界，即状态，在每个状态可以选择范围内任意位置作为最后戳破气球的位置。
③．边界与初始化
i，j 分别代表子区间的边界、并且区间内包含有气球，所有 j >= i+1，并且 i 、j 都不等于数组的左右边界。
初始化所有状态的值为 0。
④．状态转移方程
假设选择 k 做为区间 (i,j) 中最后戳破的气球，则dp[i[j]=dp[i[k]+dp[k[j]+nums[k]*nums[i]*nums[j]；在范围 (i,j) 内枚举所有的 k ,然后求 dp[i[j] 的最大值即可。
状态 dp[i[j] 是由 dp[i[k] 和 dp[k[j] 得到的，其中 i < k < j，所以需要在计算 dp[i[j] 时，状态 dp[i[k] 和 dp[k[j] 已经有值。

因此 i 需要从下往下进行遍历（确保 j 固定时，所有的 dp[k][j] 已经有值）、j 需要从左往右进行遍历（确保 i 固定时，所有的 dp[i][k] 已经有值）。
⑤．确认结果
dp[0][nums.size()-1] 即最终的返回结果。
⑥．代码示例

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        nums.insert(nums.begin(),1);// 开头添加元素
        nums.insert(nums.end(),1);// 末尾添加元素
        // dp 初始化所有值为 0
        vector<vector<int>> dp(nums.size(),vector(nums.size(),0));
        // 从下往上 枚举左边界
        for( int i = nums.size()-3;i >= 0;i --)
        {
            // 从 左往右枚举 边界
            for( int j = i+2;j <= nums.size()-1;j++ )
            {
                // 枚举所有选择：最后戳破气球的位置
                for( int k = i+1;k < j;k++)
                {
                    dp[i][j] = max(dp[i][j],dp[i][k] + dp[k][j] + nums[k]* nums[i]*nums[j]);
                }
            }
        }
        // 返回结果
        return dp[0][nums.size()-1];    
    }
};