NUMBER OF OPERATIONS TO EXHAUST A STRING DELETING ONLY PALINDROMES | HARD | MUST DO

https://practice.geeksforgeeks.org/problems/minimum-steps-to-delete-a-string2956/1?utm_source=gfg&utm_medium=article&utm_campaign=bottom_sticky_on_article

Given string s containing characters as integers only, the task is to delete all characters of this string in a minimum number of steps wherein one step you can delete the substring which is a palindrome. After deleting a substring remaining parts are concatenated.

Example 1:

Input: s = "2553432"
Output: 2
Explanation: In first step remove "55",
then string becomes "23432" which is a
palindrome.
Example 2:
Input: s = "1234"
Output: 4
Explanation: Remove each character in
each step

---------------------------------------------------------------------------------------------------------------------------------------
class Solution{
    public:
    int minStepToDeleteString(string s) {
        int n=s.size();
        vector<vector<int>> dp(n,vector<int>(n,0));
        for(int i=0;i<n;i++){
            dp[i][i]=1;  // erasing a single character
        }
        for(int i=0;i<n-1;i++){
            if(s[i]==s[i+1]){
                dp[i][i+1]=1;  // deleting the palindrome of size 2
            }
            else{
                dp[i][i+1]=2; // deleting two character
            }
        }
        for(int len=3;len<=n;len++){
            for(int start=0;start<=n-len;start++){
                int end=start+len-1;
                if(s[start]==s[end]){
                    dp[start][end]=dp[start+1][end-1];
                }
                else{
                    dp[start][end]=1+min(dp[start][end-1],dp[start+1][end]);
                }
                for(int par=start;par<end;par++){ // break it in two parts
                    dp[start][end]=min(dp[start][end],dp[start][par]+dp[par+1][end]);
                }
            }
        }
        return dp[0][n-1];
    }
};

CAN YOU FIGURE OUT A RECURSIVE SOLUTION, MR. BABOON?