Giả sử chúng ta có một mảng số nguyên tên arr, bây giờ trong một nước đi chúng ta có thể chọn một dãy con đối xứng từ chỉ số i đến j với i <= j, và xóa dãy con đó khỏi mảng cho trước. Chúng ta phải nhớ rằng sau khi xóa dãy con, các phần tử bên trái và bên phải của dãy con đó di chuyển để lấp đầy khoảng trống do việc xóa. Chúng ta phải tìm số nước đi tối thiểu cần thiết để xóa tất cả số từ mảng.
Vì vậy, nếu đầu vào là arr = [1,3,4,1,5], đầu ra sẽ là 3, vì chúng ta có thể xóa theo trình tự: xóa [4] sau đó xóa [1,3,1] rồi xóa [5].
Để giải quyết, chúng ta sẽ làm theo các bước:
n := kích thước của arr
Định nghĩa mảng 2D dp kích thước (n + 1) x (n + 1)
Khởi tạo l := 1, khi l <= n, cập nhật (tăng l lên 1), làm:
Khởi tạo i := 0, j := l - 1, khi j < n, cập nhật (tăng i lên 1), (tăng j lên 1), làm:
nếu l giống 1, thì:
dp[i, j] := 1
Ngược lại
dp[i, j] := 1 + dp[i + 1, j]
nếu i + 1 < n và arr[i] giống arr[i + 1], thì:
dp[i, j] := nhỏ nhất của dp[i, j] và 1 + dp[i + 2, j]
Khởi tạo k := i + 2, khi k <= j, cập nhật (tăng k lên 1), làm:
nếu arr[i] giống arr[k], thì:
dp[i, j] := nhỏ nhất của dp[i, j] và dp[i + 1, k - 1] + dp[k + 1, j]
Trả về dp[0, n - 1]
Hãy xem triển khai sau để hiểu rõ hơn:
Ví dụ
#include <bits/stdc++.h> using namespace std; class Solution { public: int minimumMoves(vector<int>& arr) { int n = arr.size(); vector<vector<int> > dp(n + 1, vector<int>(n + 1)); for (int l = 1; l <= n; l++) { for (int i = 0, j = l - 1; j < n; i++, j++) { if (l == 1) { dp[i][j] = 1; } else { dp[i][j] = 1 + dp[i + 1][j]; if (i + 1 < n && arr[i] == arr[i + 1]) dp[i][j] = min(dp[i][j], 1 + dp[i + 2][j]); for (int k = i + 2; k <= j; k++) { if (arr[i] == arr[k]) { dp[i][j] = min(dp[i][j], dp[i + 1][k - 1] + dp[k + 1][j]); } } } } } return dp[0][n - 1]; } }; main(){ Solution ob; vector<int> v = {1,2}; cout << (ob.minimumMoves(v)); }Đầu vào
[1,2]
Đầu ra
2