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]
|
Nếu cần chia mảng thành chính xác k phân đoạn con, thì tham số thứ hai chỉ cần được thêm vào trong lập trình động - chia thành bao nhiêu phân đoạn.
Đó là, bây giờ chúng ta sẽ xem xét dp sau:
dp[i][j] là câu trả lời cho i phần tử đầu tiên, nếu chúng ta chia chúng thành chính xác j phân đoạn.
Coi chừng các trạng thái không hợp lệ.
Việc tính toán lại các động lực là như nhau, nhưng có tính đến tham số thứ hai. Nghĩa là, đếm dp[i][k] và sắp xếp qua đường viền bên trái của phân đoạn con j cuối cùng, chúng tôi tính toán lại dp[i][k] đến dp[j - 1][k - 1] và giá trị của phân đoạn [j;i].
|
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 có một tập hợp các khoảng trống nằm trên một số trục (thường là trục thời gian hoặc chỉ số của một số mảng) và bạn cần chọn một số trong số chúng theo cách tối ưu để các khoảng trống đã chọn không giao nhau, thì bạn nên thử sử dụng lập trình động .
Sơ đồ giải pháp gần đúng:
Ban đầu, chúng tôi sắp xếp các khoảng trống có sẵn theo đường viền bên phải. Hãy bắt đầu động lực học sau: dp[i] - câu trả lời cho khoảng i đầu tiên.
Ta sẽ tính lại như sau: đầu tiên xét trường hợp khoảng này sẽ không được sử dụng, khi đó chỉ cần dp[i] = dp[i-1]. Lưu ý rằng điều này đảm bảo rằng các giá trị của dp[i] không giảm khi tôi lớn lên. Và điều này là hợp lý, bởi vì. thêm một khoảng cách mới, chúng ta không thể làm xấu đi câu trả lời toàn cầu: hoặc chúng ta đơn giản bỏ qua khoảng cách mới hoặc chúng ta xây dựng một biến thể có lợi hơn bằng cách sử dụng nó. Bây giờ, nếu chúng ta muốn sử dụng khoảng cách thứ i, thì chúng ta có thể sử dụng những khoảng trống có đường viền bên phải nhỏ hơn đường viền bên trái của khoảng cách hiện tại, vì chúng ta phải chọn một tập hợp các khoảng trống không chồng lấp. Để làm điều này, ban đầu chúng tôi đã sắp xếp các khoảng trống theo đường viền bên phải, để bây giờ chúng tôi có thể tìm thấy vị trí cần thiết một cách hiệu quả. Điều này có thể được thực hiện một cách phân tích, nếu có thể, nhưng trong trường hợp chung, có thể tìm thấy một khoảng cách với một binsearch, đường viền bên phải nhỏ hơn đường viền bên trái của đường viền hiện tại, đồng thời, mức tối đa có thể một. Chúng tôi muốn tối đa hóa đường viền bên phải vì lý do tham lam, bởi vì khi tôi lớn lên, câu trả lời chỉ có thể tăng lên. Theo đó, chúng ta tìm vị trí p cần thiết và tính toán lại từ dp[i] đến dp[p] và khoảng thứ i.
|