Giả sử chúng ta có một tập hợp các viên đá, mỗi viên có trọng lượng là số nguyên dương. Mỗi lượt, ta chọn hai viên đá bất kỳ và đập chúng vào nhau. Nếu hai viên đá có trọng lượng x và y với x ≤ y. Kết quả của cú đập này sẽ là:
Nếu x = y, cả hai viên đá đều bị phá hủy hoàn toàn;
Nếu x ≠ y, viên đá có trọng lượng x bị phá hủy hoàn toàn, và viên đá có trọng lượng y có trọng lượng mới là y - x.
Cuối cùng, chỉ còn lại tối đa 1 viên đá. Ta cần tìm trọng lượng nhỏ nhất có thể của viên đá này (trọng lượng là 0 nếu không còn viên đá nào).
Ví dụ, nếu đầu vào là [2,7,4,1,8,1], thì đầu ra sẽ là 1. Bởi vì nếu ta đập (2,4), mảng mới sẽ là [2,7,1,8,1], sau đó đập (7,8), mảng mới sẽ là [2,1,1,1], rồi đập (2,1), mảng sẽ là [1,1,1], sau đó đập (1,1), chỉ còn lại 1.
Để giải quyết bài toán này, ta thực hiện các bước sau:
n := kích thước mảng stones, total := 0
Với i từ 0 đến n - 1: total := total + stones[i]
req := total / 2
Tạo mảng dp kích thước req + 1, điền giá trị false
dp[0] := true, reach := 0
Với i từ 0 đến n - 1:
Với j từ req giảm dần đến stones[i]:
dp[j] := dp[j] || dp[j - stones[i]]
Nếu dp[j] là true, reach := max(reach, j)Trả về total - (2 * reach)
Xem ví dụ triển khai dưới đây để hiểu rõ hơn:
Ví dụ
#include <bits/stdc++.h> using namespace std; class Solution { public: int lastStoneWeightII(vector<int>& stones) { int n = stones.size(); int total = 0; for(int i = 0; i < n; i++){ total += stones[i]; } int req = total / 2; vector <bool> dp(req + 1, false); dp[0] = true; int reach = 0; for(int i = 0; i < n; i++){ for(int j = req; j - stones[i] >= 0; j--){ dp[j] = dp[j] || dp[j - stones[i]]; if(dp[j]) reach = max(reach, j); } } return total - (2 * reach); } }; int main(){ vector<int> v = {2,7,4,1,8,1}; Solution ob; cout << (ob.lastStoneWeightII(v)); }Đầu vào
[2,7,4,1,8,1]
Đầu ra
1