i have a question for dynamic programming can anyone help me to solve this ?
we have a sequence of character and have a set of sub sequence …
i want to find largest sub sequence contain this set
for example :
input :
A AB BA CA BBC
.
ABABACABAABC
out put :
11 : ABABACABAAB
output explain :
first see A
we can create it by A in set.
next have AB
can create by AB
next have ABA
can create with A and AB
Can you explain the output??
Are you trying to say that we are given a original string and a number of substrings and we have to obtain maximum size of string by combining these substrings that must be present in the original string.
i think this problem is similiar to codeforces global round 3 - problem A
if i m right then …
this problem is not the dynamic programming problem
it’s a simple math problem
link of codeforces problem A
ye i understand its not dp but it is not true solution … we have set of any character … but this problem had 3 char and they can comlex … A B AB BA CA …
I think the approach is that you have to check all the possibilities for a given string.
See, in this example,in the beginning for string ABABACABAABC we have two options :-A and AB.
So, what we do we will check for both cases, we make a recursive function in which two parameters are passed. The first one will be new string and the second one will be the length we have traversed.And this way we proceed.
And we will return the value which will give us the maximum length.
MY code-
// In this code i assumed that the number of substrings are given.
#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<string> v;
int count1=0;
int recursion(string s, int l)
{
int k = l;
if(s.length()==0) return 0;
for(int j=0;j<v.size();j++)
{
l=k;
string k = v[j];
if(s.substr(0,k.length())==k)
{
recursion(s.substr(k.length(),s.length()-k.length()),l+= k.length());
}
count1=max(count1,l);
}
return count1;
}
int main()
{
string s;
cin>>s;
int n;
cin>>n;
cin.ignore();
for(int i=0;i<n;i++) {
string p;
cin>>p;
v.push_back(p);
}
cout<<recursion(s,0)<<endl;