Cho n bóng bay, bóng i có giá trị nums[i]. Phá bóng i thu được nums[i-1] * nums[i] * nums[i+1] xu (coi bóng ảo ở 2 đầu có giá trị 1). Sau khi phá, 2 bên liền kề trở thành hàng xóm. Tối đa hóa tổng xu.
Ví dụ
nums = [3,1,5,7]
Phá theo thứ tự: 1 → 5 → 3 → 7
- Phá 1: 3×1×5 = 15, mảng: [3,5,7]
- Phá 5: 3×5×7 = 105, mảng: [3,7]
- Phá 3: 1×3×7 = 21, mảng: [7]
- Phá 7: 1×7×1 = 7
- Tổng: 148
Thuật toán: DP khoảng (Interval DP)
dp[l][r] = tối đa xu từ phá tất cả bóng trong khoảng [l, r] (kể cả 2 đầu).
Xét bóng i là bóng cuối cùng phá trong [l, r]:
coins = dp[l][i-1] + dp[i+1][r] + nums[l-1] * nums[i] * nums[r+1] dp[l][r] = max over i
Điền DP theo chiều dài khoảng tăng dần.
Cài đặt C++
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxCoins(vector<int>& a) {
int n = a.size();
if (!n) return 0;
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int l = n - 1; l >= 0; l--) {
for (int r = l; r < n; r++) {
for (int i = l; i <= r; i++) {
int left = (i - 1 >= 0) ? dp[l][i-1] : 0;
int right = (i + 1 < n) ? dp[i+1][r] : 0;
int leftVal = (l - 1 >= 0) ? a[l-1] : 1;
int rightVal = (r + 1 < n) ? a[r+1] : 1;
dp[l][r] = max(dp[l][r], left + right + leftVal * rightVal * a[i]);
}
}
}
return dp[0][n-1];
}
};
int main() {
Solution ob;
vector<int> v = {3, 1, 5, 7};
cout << ob.maxCoins(v);
return 0;
}
Độ phức tạp
- Thời gian:
O(n^3)— 3 vòng lặp lồng. - Không gian:
O(n^2)— bảng DP.
Input / Output
Input: [3,1,5,7] Output: 148