Program to find number of operations required to remove palindromic sublists in C++

Suppose we have a list of numbers called nums. Now let us consider an operation where we delete some sublist which is a palindrome. We have to find the minimum number of operations required such that the list is empty.

So, if the input is like nums = [6, 2, 4, 4, 2, 10, 6], then the output will be 2, as we can remove the sublist [2, 4, 4, 2] first then the list is like [6, 10, 6] this is also a palindrome, so remove it to make list empty.

To solve this, we will follow these steps −

• Define an array dp of size: 105 x 105.

• Define a function dfs(), this will take i, j, an array v,

• ret := inf

• if i > j, then −

  • return 0

• if i is same as j, then −

  • return 1

• if j - i is same as 1, then −

  • return (if v[i] is same as v[j], then 1, otherwise 2)

• if i + 1 <= j and v[i] is same as v[i + 1], then −

  • ret := 1 + dfs(i + 2, j, v)

• if dp[i, j] is not equal to -1, then −

  • return dp[i, j]

• ret := minimum of (ret, 1 + (minimum of (dfs(i + 1, j, v) and dfs(i, j - 1, v)))

• if v[i] is same as v[j], then −

  • ret := minimum of ret and dfs(i + 1, j - 1, v)

• for initialize k := i + 2, when k < j, update (increase k by 1), do −

  • if v[i] is same as v[k], then &minnus;

    • ret := minimum of ret and dfs((i + 1, k - 1, v) + dfs(k + 1, j, v))

• return dp[i, j] = ret

• From the main method do the following −

• fill dp with -1

• n := size of nums

• return dfs(0, n - 1, nums)

Example  

Let us see the following implementation to get better understanding −

 Live Demo

#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);    int n = nums.size();    return dfs(0, n - 1, nums); } int main(){    vector<int> v = {6, 2, 4, 4, 2, 10, 6};    cout << solve(v); }

Input

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

Output

2