Получение неправильного ответа в проблеме DP, хотя реализация выглядит правильно

Question

Я пытался решить Уменьшить строку в коде, который говорит: «Дайте строку s длины l и набор S из n примерных строк». Мы сокращаем строку s, используя набор S, следующим образом: где Si появляется в качестве последовательной подстроки строки s, вы можете удалить (или нет) ее. После каждого удаления вы получите новую строку s, соединив часть слева и справа от удаленной подстроки.

Я написал рекурсивную функцию следующим образом: - В основном, что я делаю в своем коде либо не удаляйте символ, либо удаляйте его, если он является частью какой-либо подстроки, но он дает неправильный ответ.

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

int dp[mx];
unordered_map<string,int> sol;

void init(int n)
{
    for(int i=0;i<n;i++)
    {
        dp[i]=-1;
    }
}

int solve(string str,int low,int high,vector<string> smp)
{
     if(low>high)
     {
        return 0;
     }
     if(dp[low]!=-1)
     {
        return dp[low];
     }
     int ans=1+solve(str,low+1,high,smp);
     for(int i=low;i<high;i++)
     {
        string tem=str.substr(low,i-low+1);
        for(int j=0;j<smp.size();j++)
        {
            cout<<"low i high str"<<low<<" "<<i<<" "<<high<<" "<<smp[j]<<" "<<tem<<endl;
            if(tem.compare(smp[j])==0)
            {
                ans=min(ans,solve(str,i+1,high,smp));
            }
        }
     }
     return dp[low]=ans;
}

signed main()
{
    sol.clear();
    string str;
    vector<string> smp;
    int n;
    cin>>str;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        string tem;
        cin>>tem;
        smp.push_back(tem);
    }
    int len=str.length();
    init(len+1);
    cout<<solve(str,0,len-1,smp)<<endl;
    return 0;
}

PS: ссылка на вопрос

Answer 1

Этот вопрос является самым сложным (замеченным до сих пор) и самым красивым (снова замеченным пока) вопросом, основанным на DP ON INTERVALS.
Исходный код определенно не будет работать, поскольку он рассматривает только один проход в строке и не будет учитывать оставшуюся строку после повторного удаления образцов.
Существует 3 случая: -
Случай 1 Ни один из символов не удаляется.
Случай 2 Он удаляется как часть непрерывной подстроки.
Случай 3 Он удаляется как часть подпоследовательности, которая соответствует любому слову, данному в наборе шаблонов, и всему, что не является частью эта подпоследовательность сначала удаляется как подстрока (которая снова принадлежит набору слов).
Третья часть самая хитрая, требует достаточного мышления и еще сложнее в реализации.
Так что для каждой подстроки нам нужно проверьте, может ли эта подстрока быть полностью уничтожена или нет. Функция compute_full_recur () - это функция, которая обеспечивает возможность удаления подстроки в случае 2 или случае 3 .
Функция compute_full заботится из Случай 1 .
И, наконец, этот код не будет работать по ссылке codechef, так как все функции рекурсивны с запоминанием, но для проверки работоспособности кода я запустил его для Задачи Reducto из Hackerrank, который в точности аналогичен нижним ограничениям. Загрузите тестовые наборы, а затем запустите тестовые наборы на вашем P C для проверки.

#include <iostream>
#include <vector>
#include <string>
using namespace std;
#define mx 252
#define nx 40
bool full[mx][mx],vis[mx][mx],full_recur[mx][mx][nx][nx];
int ans[mx];

void init()
{
    for(int i=0;i<mx;i++)
    {
        for(int j=0;j<mx;j++)
        {
            full[i][j]=false,vis[i][j]=false;
        }
    }

    for(int i=0;i<mx;i++)
    {
        ans[i]=-1;
    }

    for(int i=0;i<mx;i++)
    {
        for(int j=0;j<mx;j++)
        {
            for(int k=0;k<nx;k++)
            {
                for(int l=0;l<nx;l++)
                {
                    full_recur[i][j][k][l]=false;
                }
            }
        }
    }

}

bool compute_full_recur(string str,int low,int high,vector<string> pat,int idx,int len)
{
    if(low>high&&len==pat[idx].length())
    {
        return true;
    }
    if(low>high&&len<pat[idx].length())
    {
        full_recur[low][high][idx][len]=false;
        return false;
    }
    if(str[low]==pat[idx][len]&&compute_full_recur(str,low+1,high,pat,idx,len+1))
    {
        return full_recur[low][high][idx][len]=true;
    }
    for(int i=low+1;i<=high;i++)
    {
        if(str[low]==pat[idx][len]&&full[low+1][i]&&compute_full_recur(str,i+1,high,pat,idx,len+1))
        {
            return full_recur[low][high][idx][len]=true;
        }
    }
    full_recur[low][high][idx][len]=false;
    return false;
}

void compute_full(string str,int low,int high,vector<string> pats)
{
    if(low>high)
    {
        return;
    }
    if(vis[low][high])
    {
        return;
    }
    vis[low][high]=true;
    compute_full(str,low+1,high,pats);
    compute_full(str,low,high-1,pats);
    for(int i=0;i<pats.size();i++)
    {
        if(!full[low][high])
        full[low][high]=compute_full_recur(str,low,high,pats,i,0);
    }
}

int compute_ans(string str,int low,int high)
{
    if(low>high)
    {
        return 0;
    }
    if(ans[low]!=-1)
    {
        return ans[low];
    }
    int sol=1+compute_ans(str,low+1,high);
    for(int i=low+1;i<=high;i++)
    {
        if(full[low][i]==true)
        {
            sol=min(sol,compute_ans(str,i+1,high));
        }
    }
    return ans[low]=sol;
}

signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        string str;
        int n;
        vector<string> pats;
        cin>>n>>str;
        for(int i=0;i<n;i++)
        {
            string tem;
            cin>>tem;
            pats.push_back(tem);
        }
        init();
        compute_full(str,0,str.length()-1,pats);
        cout<<compute_ans(str,0,str.length()-1)<<endl;
    }
    return 0;
}