สมมติว่าเรามีอาร์เรย์จำนวนเต็มที่เรียกว่า arr ในการย้ายครั้งเดียว เราสามารถเลือก subarray palindromic จากดัชนี i ถึง j โดยที่ i <=j และลบอาร์เรย์ย่อยนั้นออกจากอาร์เรย์ที่กำหนด เราต้องจำไว้ว่าหลังจากลบ subarray แล้ว องค์ประกอบทางด้านซ้ายและด้านขวาของ subarray นั้นจะย้ายเพื่อเติมช่องว่างที่เหลือโดยการลบ เราต้องหาจำนวนการเคลื่อนไหวขั้นต่ำที่จำเป็นในการลบตัวเลขทั้งหมดออกจากอาร์เรย์
ดังนั้นหากอินพุตเป็นเหมือน arr =[1,3,4,1,5] ผลลัพธ์จะเป็น 3 ตามที่เราสามารถลบในลำดับนี้ได้ ลบ [4] จากนั้นลบ [1,3,1] แล้ว ลบ [5].
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
n :=ขนาดของ arr
-
กำหนดขนาดอาร์เรย์ 2 มิติหนึ่ง dp (n + 1) x (n + 1)
-
สำหรับการเริ่มต้น l :=1 เมื่อ l <=n อัปเดต (เพิ่ม l ขึ้น 1) ทำ −
-
สำหรับการเริ่มต้น i :=0, j :=l - 1, เมื่อ j
-
ถ้า l เท่ากับ 1 แล้ว −
-
dp[i, j] :=1
-
-
มิฉะนั้น
-
dp[i, j] :=1 + dp[i + 1, j]
-
ถ้า i + 1
-
dp[i, j] :=ขั้นต่ำของ dp[i, j] และ 1 + dp[i + 2, j]
-
-
สำหรับการเริ่มต้น k :=i + 2 เมื่อ k <=j อัปเดต (เพิ่ม k ขึ้น 1) ทำ −
-
ถ้า arr[i] เหมือนกับ arr[k] แล้ว −
-
dp[i, j] :=ขั้นต่ำของ dp[i, j] และ dp[i + 1, k - 1] + dp[k + 1, j]
-
-
-
-
-
-
กลับ dp[0, n - 1]
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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));
} อินพุต
[1,2]
ผลลัพธ์
2
