标签：nums int 312 气球 DP 区间 balloons LeetCode dp

题目链接

312. 戳气球

思路

参考动态规划套路解决戳气球问题

分析动态规划题目的时候只需要考虑最后一个阶段，因为所有的阶段转化都是相同的，考虑最后一个阶段容易发现规律

在数组的动态规划问题中，一般 dp[i] 都是表示以 nums[i] 为结尾的状态；dp[i][j] 分别表示 以 nums1[i] 和 nums2[j] 为结尾的状态，以此类推

字符串也是个数组，是字符数组

很明显这是一道区间dp，区间dp最基本的思想就是将大区间拆分成多个小区间的组合求解，假如说我们有个区间 \([i, j]\)，中间有多个分割点 \(k_1, k_2, \dots, k_m\)，那么区间dp的状态转移公式一般为：

\[dp[i][j] = f(dp[i][j], g(dp[i][k_1], dp[k_1][k_2], \dots, dp[k_m][j])) \]

表示状态

状态表示就是靠猜，但是会有猜的套路，一般都是通过最终结果和数组数量来猜

找状态转移方程

思考的方向是：大问题的最优解怎么由小问题的最优解得到

边界处理

代码

dp数组版

class Solution {
    public int maxCoins(int[] nums) {
        // 两端创建虚拟气球
        int n = nums.length;
        int[] balloons = new int[n + 2];
        balloons[0] = balloons[n + 1] = 1;
        for(int i = 1; i < n + 1; i++){
            balloons[i] = nums[i - 1];
        }

        int[][] dp = new int[n + 3][n + 3];
        // 枚举区间长度
        for(int len = 1; len <= n + 2; len++){
            // 枚举起点
            for(int i = 0; i + len - 1 < n + 2; i++){
                // 枚举终点
                int j = i + len - 1;
                if(len == 1 || len == 2){
                    dp[i][j] = 0;
                }
                // 枚举分割点
                for(int k = i + 1; k <= j - 1; k++){
                    // 状态转移
                    dp[i][j] = Math.max(
                            dp[i][j],
                            dp[i][k] + dp[k][j] + balloons[i] * balloons[k] * balloons[j]
                    );
                }
            }
        }

        return dp[0][n + 1];
    }
}

标签：nums,int,312,气球,DP,区间,balloons,LeetCode,dp
From： https://www.cnblogs.com/shixuanliu/p/17339360.html