โปรแกรมนับจำนวนการดำเนินการลบสับลิสต์พาลินโดรมใน C++

ให้ลิสต์ตัวเลข nums ดำเนินการลบสับลิสต์ที่เป็นพาลินโดรม หาจำนวนครั้งน้อยที่สุดเพื่อให้ลิสต์ว่างเปล่า

ตัวอย่าง: nums = [6, 2, 4, 4, 2, 10, 6] → 2 ครั้ง ลบ [2,4,4,2] ก่อน เหลือ [6,10,6] ซึ่งเป็นพาลินโดรม ลบอีกครั้งจบ

ขั้นตอนการแก้ปัญหา (DP + Memoization)

1. dp[105][105] เริ่มต้น -1
2. ฟังก์ชัน dfs(i, j, v):
   • ถ้า i > j: คืน 0
   • ถ้า i == j: คืน 1
   • ถ้า j-i == 1: คืน (v[i]==v[j] ? 1 : 2)
   • ถ้า v[i]==v[i+1]: ret = 1 + dfs(i+2, j)
   • ถ้า dp[i][j] != -1: คืน dp[i][j]
   • ret = min(ret, 1 + min(dfs(i+1,j), dfs(i,j-1)))
   • ถ้า v[i]==v[j]: ret = min(ret, dfs(i+1, j-1))
   • วน k = i+2 ถึง j-1: ถ้า v[i]==v[k]: ret = min(ret, dfs(i+1,k-1)+dfs(k+1,j))
   • dp[i][j] = ret, คืน ret
3. เติม dp ด้วย -1, เรียก dfs(0, n-1, nums)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

int dp[105][105];

int dfs(int i, int j, vector<int>& v) {
    int ret = INT_MAX;
    if (i > j) return 0;
    if (i == j) return 1;
    if (j - i == 1) return v[i] == v[j] ? 1 : 2;
    if (i + 1 <= j && v[i] == v[i+1])
        ret = 1 + dfs(i+2, j, v);
    if (dp[i][j] != -1) return dp[i][j];
    ret = min({ret, 1 + min(dfs(i+1, j, v), dfs(i, j-1, v))});
    if (v[i] == v[j])
        ret = min(ret, dfs(i+1, j-1, v));
    for (int k = i+2; k < j; k++)
        if (v[i] == v[k])
            ret = min(ret, dfs(i+1, k-1, v) + dfs(k+1, j, v));
    return dp[i][j] = ret;
}

int solve(vector<int>& nums) {
    memset(dp, -1, sizeof dp);
    return dfs(0, nums.size()-1, nums);
}

int main() {
    vector<int> v = {6, 2, 4, 4, 2, 10, 6};
    cout << solve(v);
    return 0;
}

อินพุต

{6, 2, 4, 4, 2, 10, 6}

เอาต์พุต

2