Tuyên bố miễn trừ trách nhiệm: Phương pháp được mô tả bên dưới không phổ biến nhưng thường có thể giải quyết vấn đề hoặc giúp bạn tìm ra giải pháp phù hợp.
Nếu vấn đề bắt nguồn từ việc cần phải chia mảng thành các phân đoạn con không giao nhau (một chuỗi các phần tử liên tiếp) theo cách tối ưu (hoặc đếm số lượng các phần tách phù hợp), thì bạn nên cố gắng giải quyết nó. sử dụng lập trình động.
Sơ đồ giải pháp ví dụ như sau:
dp[i] - phản hồi cho phần tử i đầu tiên
Đếm dp[i]: vì chúng ta chỉ xem xét các phần tử thứ i đầu tiên, nên phần tử thứ i sẽ là phần tử cuối cùng, có nghĩa là phần tử này sẽ nằm trong phân đoạn con cuối cùng, đồng thời, phần tử ngoài cùng bên phải ở đó. Do đó, chúng ta có thể lặp qua ranh giới bên trái của phân đoạn con j cuối cùng. Trong quá trình liệt kê, chúng tôi sẽ tính toán giá trị của phân đoạn con này và nếu nó đúng, thì chúng tôi sẽ tính toán lại từ dp[i] đến dp[j - 1] và giá trị của phân đoạn con [j;i].
Hãy xem xét vấn đề đơn giản sau: cho một mảng các số nguyên, bạn cần chia nó thành số lượng tối thiểu các phân đoạn con không giao nhau để mỗi số được bao gồm trong một số phân đoạn con và mỗi phân đoạn con chứa các số giống nhau. Ví dụ: đối với mảng 1 2 2 3 3 3 2 1 1, phân vùng tối ưu có dạng như sau: [1] [2 2] [3 3 3] [2] [1 1]. Nhiệm vụ này có thể giải quyết dễ dàng bằng cách đơn giản là chuyển qua mảng (chúng ta đặt tất cả các phần tử liên tiếp giống nhau vào một phân đoạn con), nhưng chúng ta sẽ giải quyết nó bằng lập trình động chẳng hạn.
intn;
cin>> N;
// điền vào mảng với 1 chỉ mục
véc tơ mảng(n + 1);
cho (int i = 1; i <= n; i++)
cin>> mảng[i];
// ban đầu đặt giá trị +oo thành dp
vecto dp(n + 1, 1000000000);
// một mảng có độ dài bằng 0 không cần phải chia, vì vậy câu trả lời cho nó là 0
dp[0] = 0;
// đếm câu trả lời cho dp[i] tăng dần i
for (int i = 1; i <= n; i++) {
// hiện tại arr[i] là phần tử cuối cùng nên nó sẽ là số ngoài cùng bên phải của phân đoạn con cuối cùng
// lặp qua tất cả các tùy chọn nơi bắt đầu phân đoạn con cuối cùng này
for (int j = i; j > 0; j--) {
nếu (mảng[j] != mảng[i]) {
// nếu bạn gặp phần tử không bằng phần tử cuối cùng thì phân đoạn con sẽ chứa các số khác nhau và điều này không thỏa mãn điều kiện
// không có điểm nào để tiếp tục, bởi vì dịch chuyển đường viền trái sang trái, phần tử này sẽ không biến mất, vì vậy chúng tôi ngắt
phá vỡ;
}
// hãy tưởng tượng đoạn con cuối cùng là [j;i]
// vì vậy bạn cần lấy phân vùng tối ưu của các phần tử j-1 đầu tiên và thêm 1 (chính phân đoạn [j; i])
dp[i] = min(dp[i], dp[j - 1] + 1);
}
}
cout << dp[n];
Nếu các phần tử có thể không thuộc bất kỳ phân đoạn con nào, thì bạn chỉ cần xem xét tùy chọn thích hợp, như dp[i] = dp[i - 1]