Palindrome Removal (การลบพาลินโดรม) ใน C++

สมมติว่าเรามีอาเรย์จำนวนเต็มชื่อ arr ตอนนี้ในหนึ่งการเคลื่อนไหว เราสามารถเลือก subarray ที่เป็นพาลินโดรม (palindromic subarray) จากดัชนี i ถึง j โดยที่ i ≤ j และลบ subarray นั้นออกจากอาเรย์ที่ให้มา เราต้องจำไว้ว่าหลังจากลบ subarray องค์ประกอบทางซ้ายและขวาของ subarray นั้นจะเคลื่อนที่มาเติมช่องว่างที่เหลือจากการลบ เราต้องหาจำนวนการเคลื่อนไหวน้อยที่สุดที่จำเป็นเพื่อลบตัวเลขทั้งหมดออกจากอาเรย์

ดังนั้น หากอินพุทคือ arr = [1,3,4,1,5] ผลลัพธ์จะเป็น 3 เนื่องจากเราสามารถลบได้ในลำดับนี้: ลบ [4] แล้วลบ [1,3,1] แล้วลบ [5]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:

• n := ขนาดของ arr

• กำหนดอาเรย์ 2 มิติ dp ขนาด (n+1) x (n+1)

• for l := 1 ถึง n:

  • for i := 0, j := l-1; j < n; i++, j++:

    • ถ้า l == 1: dp[i][j] := 1

    • มิฉะนั้น:

      • dp[i][j] := 1 + dp[i+1][j]

      • ถ้า i+1 < n และ arr[i] == arr[i+1]: dp[i][j] := min(dp[i][j], 1 + dp[i+2][j])

      • for k := i+2 ถึง j:

        • ถ้า arr[i] == arr[k]: dp[i][j] := min(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& arr) {
        int n = arr.size();
        vector> dp(n + 1, vector(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];
    }
};

int main() {
    Solution ob;
    vector v = {1, 2};
    cout << (ob.minimumMoves(v));
    return 0;
}

อินพุต

[1,2]

เอาต์พุต

2