题目链接

思路

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

在数组的动态规划问题中，一般 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];
    }
}