如何将这种递归解转换为分而治之？

Question

如何解答这个问题：给定 n 个气球，索引从 0 到 n-1。每个气球上都画有一个由数组 nums 表示的数字。你被要求爆破所有的气球。如果你爆破气球，你将获得 nums[left] * nums[right] 个硬币。这里 left 和 right 是 i 的相邻索引。爆破后，左右就会变得相邻。如果你爆破角气球，那么你将得到与这些气球相邻的点。如果你爆破最后一个气球，那么你将得到上面写的点数。明智地爆破气球，找到可以收集的最多硬币。测试用例示例：{1,2,3,4}20{5,7,8}56我已经尝试使用递归来解决这个问题，这似乎给出了正确的答案：public static int maxCoints(List<Integer> list) {        int max = 0;        if (list.size() == 1) {            return list.get(0);        }        if(list.size() == 2) {            return Math.max(list.get(0),list.get(1))*2;        }        for (int i = 0; i < list.size(); i++) {            int left = i == 0 ? 1 : list.get(i-1);            int right = i == list.size()-1 ? 1 : list.get(i+1);            int n = left * right;            List<Integer> tmp = new ArrayList<>(list);            tmp.remove(i);            max = Math.max(max, n + maxCoints(tmp));        }        return max;    }但我已经尝试过这种分而治之的解决方案，但它似乎对第一个测试用例给出了错误的答案，这给出了答案 17 而不是 20int find(vector<int>& v, int L, int R) {    int ans = 0;    // if(L==R)    return v[L];    for (int i = L; i <= R; i++) {        int l = find(v, L, i-1);        int r = find(v, i+1, R);        int val = v[L-1]*v[R+1] + l + r;        ans = max(ans, val);    }    return ans;}int32_t main() {fast_io;    ll tt;  cin >> tt;    while(tt--) {        ll n;   cin >> n;        vector<int> v(n+2,1);        for(int i=1;i<=n;i++) {            cin >> v[i];        }        cout << find(v,1,n) << "\n";    }    return 0;}请帮我找出错误。

Answer 1

递归可以工作，但对于我们的意图和目的来说它太慢了。递归地删除每个气球并缓存给我们提供2^N状态，这是气球的幂集。我们希望在多项式时间内解决这个问题。

分而治之绝对是正确的想法。

• 气球爆破后，我们可以将问题分为（ ）i左边的气球和（ ）右边的气球。inums[0:i]inums[i+1:]

• 为了找到最佳解决方案，我们在每个气球破裂后检查每个最佳解决方案。

• 因为我们会在 nums 中找到每个范围的最佳解决方案，并且我们会爆破每个范围中的每个气球来找到最佳解决方案，所以我们有一个O(N^2)范围O(N)乘以每个范围的时间，这是一个O(N^3)解决方案

• 然而，如果我们尝试按照气球首先破裂的顺序来划分问题，我们就会遇到问题。当气球爆炸时，其他气球的相邻位置会发生变化。我们无法跟踪间隔的端点与哪些气球相邻。这就是您的解决方案存在问题的地方。

详细说明最后一点：

当你这样做时：

int l = find(v, L, i-1);

您实际上可能无法获得最佳解决方案。考虑到气球爆裂后，气球i - 1现在与气球相邻。如果随后气球爆裂，气球现在会与气球相邻。如果您尝试在每次气球爆炸时进行划分，则您必须以某种方式仍然考虑范围之外的气球。i + 1ii - 1i - 2i + 1find[L, R]

为了解决这个问题，我们考虑将气球按与气球破裂的顺序相反的顺序添加到最初为空的区间中，而不是使气球破裂并进行划分。

让dp(i, j)表示 上的最大分数[i, j]。对于k上的每个气球[i + 1, j - 1]，我们将其添加到间隔中并计算分数。添加气球后，我们总是可以将问题分为 和[i, k]，[k, j]因为左右边界是已知的。这消除了邻接问题。

更棘手的部分是实现“如果你戳破最后一个气球，那么你将获得上面写的分数”。我们手动迭代最后一个破裂的气球，并像以前一样应用分而治之。

查看代码以获得更好的想法：

class Solution {

    public int maxCoins(int[] nums) {

        int n = nums.length + 2;

        int[] new_nums = new int[n];

        for(int i = 0; i < nums.length; i++){

            new_nums[i+1] = nums[i];

        }

        new_nums[0] = new_nums[n - 1] = 1;

        // cache the results of dp

        int[][] memo = new int[n][n];

        // find the maximum number of coins obtained from adding all balloons from (0, len(nums) - 1)

        int ans = 0;

        // manually burst the last balloon because it has special rules

        for(int i = 1; i < n; ++i){

            ans = Math.max(ans, new_nums[i] + dp(memo, new_nums, i, n - 1) + dp(memo, new_nums, 0, i));

        }

        return ans;

    }

    public int dp(int[][] memo, int[] nums, int left, int right) {

        // no more balloons can be added

        if (left + 1 == right) return 0;

        // we've already seen this, return from cache

        if (memo[left][right] > 0) return memo[left][right];

        // add each balloon on the interval and return the maximum score

        int ans = 0;

        for (int i = left + 1; i < right; ++i)

            ans = Math.max(ans, nums[left] * nums[right]

            + dp(memo, nums, left, i) + dp(memo, nums, i, right));

        // add to the cache

        memo[left][right] = ans;

        return ans;

    }

}

输入：

[1, 2, 3, 4]

[5, 7, 8]

输出：

20

56