Skip to content

Instantly share code, notes, and snippets.

@KoStard
Created August 18, 2017 14:19
Show Gist options
  • Save KoStard/acc15127c0c3ac0f1a9a3ea0e22f6dc1 to your computer and use it in GitHub Desktop.
Save KoStard/acc15127c0c3ac0f1a9a3ea0e22f6dc1 to your computer and use it in GitHub Desktop.
Dynamic programming
#include <iostream>
#include <vector>
using namespace std;
int main(){
int q;
cout << "Type the queries number: ";
cin >> q;
while(q--){
string str;
cout << "Type the text: ";
cin >> str;
int l = (int)str.length();
int arr[l][l];
for(int i=0;i<str.length();i++){
for(int j=0;j<str.length()-i;j++){
if(i==0){
arr[j][j]=1;
if(j!=str.length()-1)
arr[j+1][j]=0;
// cout << arr[j][j+i] << " ";
continue;
}
if(str[j+i]==str[j]){
arr[j][j+i]=arr[j+1][j+i-1]+2;
// cout << arr[j][j+i] << " ";
continue;
}
arr[j][j+i]=max(arr[j+1][j+i], arr[j][j+i-1]);
// cout << arr[j][j+i] << " ";
}
// cout << endl;
}
cout << arr[0][l-1] << endl;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment