如何解答這個(gè)問(wèn)題：給定 n 個(gè)氣球，索引從 0 到 n-1。每個(gè)氣球上都畫有一個(gè)由數(shù)組 nums 表示的數(shù)字。你被要求爆破所有的氣球。如果你爆破氣球，你將獲得 nums[left] * nums[right] 個(gè)硬幣。這里 left 和 right 是 i 的相鄰索引。爆破后，左右就會(huì)變得相鄰。如果你爆破角氣球，那么你將得到與這些氣球相鄰的點(diǎn)。如果你爆破最后一個(gè)氣球，那么你將得到上面寫的點(diǎn)數(shù)。明智地爆破氣球，找到可以收集的最多硬幣。測(cè)試用例示例：{1,2,3,4}20{5,7,8}56我已經(jīng)嘗試使用遞歸來(lái)解決這個(gè)問(wèn)題，這似乎給出了正確的答案：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; }但我已經(jīng)嘗試過(guò)這種分而治之的解決方案，但它似乎對(duì)第一個(gè)測(cè)試用例給出了錯(cuò)誤的答案，這給出了答案 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;}請(qǐng)幫我找出錯(cuò)誤。
1 回答
神不在的星期二
TA貢獻(xiàn)1963條經(jīng)驗(yàn) 獲得超6個(gè)贊
遞歸可以工作，但對(duì)于我們的意圖和目的來(lái)說(shuō)它太慢了。遞歸地刪除每個(gè)氣球并緩存給我們提供2^N狀態(tài)，這是氣球的冪集。我們希望在多項(xiàng)式時(shí)間內(nèi)解決這個(gè)問(wèn)題。
分而治之絕對(duì)是正確的想法。
氣球爆破后，我們可以將問(wèn)題分為（ ）
i左邊的氣球和（ ）右邊的氣球。inums[0:i]inums[i+1:]為了找到最佳解決方案，我們?cè)诿總€(gè)氣球破裂后檢查每個(gè)最佳解決方案。
因?yàn)槲覀儠?huì)在 nums 中找到每個(gè)范圍的最佳解決方案，并且我們會(huì)爆破每個(gè)范圍中的每個(gè)氣球來(lái)找到最佳解決方案，所以我們有一個(gè)
O(N^2)范圍O(N)乘以每個(gè)范圍的時(shí)間，這是一個(gè)O(N^3)解決方案然而，如果我們嘗試按照氣球首先破裂的順序來(lái)劃分問(wèn)題，我們就會(huì)遇到問(wèn)題。當(dāng)氣球爆炸時(shí)，其他氣球的相鄰位置會(huì)發(fā)生變化。我們無(wú)法跟蹤間隔的端點(diǎn)與哪些氣球相鄰。這就是您的解決方案存在問(wèn)題的地方。
詳細(xì)說(shuō)明最后一點(diǎn)：
當(dāng)你這樣做時(shí)：
int?l?=?find(v,?L,?i-1);
您實(shí)際上可能無(wú)法獲得最佳解決方案?？紤]到氣球爆裂后，氣球i - 1現(xiàn)在與氣球相鄰。如果隨后氣球爆裂，氣球現(xiàn)在會(huì)與氣球相鄰。如果您嘗試在每次氣球爆炸時(shí)進(jìn)行劃分，則您必須以某種方式仍然考慮范圍之外的氣球。i + 1ii - 1i - 2i + 1find[L, R]
為了解決這個(gè)問(wèn)題，我們考慮將氣球按與氣球破裂的順序相反的順序添加到最初為空的區(qū)間中，而不是使氣球破裂并進(jìn)行劃分。
讓dp(i, j)表示 上的最大分?jǐn)?shù)[i, j]。對(duì)于k上的每個(gè)氣球[i + 1, j - 1]，我們將其添加到間隔中并計(jì)算分?jǐn)?shù)。添加氣球后，我們總是可以將問(wèn)題分為 和[i, k]，[k, j]因?yàn)樽笥疫吔缡且阎?。這消除了鄰接問(wèn)題。
更棘手的部分是實(shí)現(xiàn)“如果你戳破最后一個(gè)氣球，那么你將獲得上面寫的分?jǐn)?shù)”。我們手動(dòng)迭代最后一個(gè)破裂的氣球，并像以前一樣應(yīng)用分而治之。
查看代碼以獲得更好的想法：
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
添加回答
舉報(bào)
0/150
提交
取消