打气球的最大得分（动态规划）

1.1. 问题

给定一个数组arr，表示一排有分数气球。每打爆一个气球都能获得分数，假设所打爆的气球分数为X，那么获得分数的规则如下：

• 如果被打爆气球的左边有没被打爆的气球，找到离被打爆气球最近的气球，假设分数为L；
  如果被打爆气球的右边有没被打爆的气球，找到离被打爆气球最近的气球，假设分数为 R。
  获得分数为 L×X×R。
• 如果被打爆气球的左边有没被打爆的气球，找到离被打爆气球最近的气球，假设分数为L；
  如果被打爆气球的右边所有气球都已经被打爆。获得分数为 L×X。
• 如果被打爆气球的左边所有的气球都已经被打爆；如果被打爆气球的右边有没被打爆的气球，找到离被打爆气球最近的气球，假设分数为 R；
  如果被打爆气球的右边所有气球都已经被打爆。获得分数为 X×R。
• 如果被打爆气球的左边和右边所有的气球都已经被打爆。获得分数为 X。

目标是打爆所有气球，获得每次打爆的分数。通过选择打爆气球的顺序，可以得到不同的总分，请返回能获得的最大分数。
要求：时间复杂度O(N³)

1.2. 解法

用F(x,y)表示在其他气球都没打爆的情况下，打爆数组arr下标范围为x～y的气球所能得到的最大得分。所以F(0,arr.length-1)即为题目要求的返回结果。
F(x,y)有以下递推关系：

1.3. 代码

先来递归的实现，注意这里对help数组前后加了两个哨兵节点，用来简化边界处理：

    public static int maxScoreRecursive(int[] arr) {
        int[] help = new int[arr.length + 2];
        help[0] = 1;
        help[help.length - 1] = 1;
        System.arraycopy(arr, 0, help, 1, arr.length);
        return process(help, 1, arr.length);
    }

    private static int process(int[] arr, int x, int y) {
        int left = arr[x - 1];
        int right = arr[y + 1];
        if (x == y) {
            return left * arr[x] * right;
        }
        int score = Math.max(process(arr, x + 1, y) + left * arr[x] * right,
                process(arr, x, y - 1) + left * arr[y] * right);
        for (int i = x + 1; i <= y - 1; i++) {
            score = Math.max(score,
                    process(arr, x, i - 1) + process(arr, i + 1, y) + left * arr[i] * right);
        }
        return score;
    }

一时间没有想到打表的方法怎么做。看了书后有些思路：

1. 首先通过递归函数的终点条件来设初始值，对本题来说是填对角线。
2. 然后确定填值的范围，对本题来说是二维数组dp中对角线以上的位置。
3. 然后确定返回值在dp上的位置，本题是dp[0][arr.length-1]，
4. 然后随机看dp矩阵上一个需要计算的位置，dp[i][j]，看计算它时依赖其他的哪些位置，从而确定打表的方向。在本题中，它依赖与同一行左边的位置的值，同一列下边位置的值，因此打表的顺序为从下往上，从左往右（当然先从左往右再从下往上也可以）。
5. 然后从起始位置开始大表，这个起始位置的判断可以结合第二点、第四点。

    public static int maxScore(int[] arr) {
        int[] help = new int[arr.length + 2];
        help[0] = help[help.length - 1] = 1;
        System.arraycopy(arr, 0, help, 1, arr.length);

        int[][] dp = new int[arr.length][arr.length];
        for (int i = 0; i < arr.length; i++) {
            dp[i][i] = help[i] * help[i + 1] * help[i + 2];
        }
        for (int i = arr.length - 2; i >= 0; i--) {
            for (int j = i + 1; j < arr.length; j++) {
                int score = Math.max(dp[i][j - 1] + help[i] * help[j + 1] * help[j + 2],
                        dp[i + 1][j] + help[i] * help[i + 1] * help[j + 2]);
                for (int k = i + 1; k <= j - 1; k++) {
                    score = Math.max(score,
                            dp[i][k - 1] + dp[k + 1][j] + help[i] * help[k + 1] * help[j + 2]);
                }
                dp[i][j] = score;
            }
        }
        return dp[0][arr.length - 1];
    }