如何解答這個問題：給定 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;}請幫我找出錯誤。
1 回答
神不在的星期二
TA貢獻1963條經驗 獲得超6個贊
遞歸可以工作，但對于我們的意圖和目的來說它太慢了。遞歸地刪除每個氣球并緩存給我們提供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
添加回答
舉報
0/150
提交
取消