stilllHungry's blog

Longest Common Subsequence
By stilllHungry, history, 8 years ago, In English

hello guys i'm new with dynamic programming this is my code for this problem and i can't understand the reason of having WA

#include <bits/stdc++.h>
using namespace std;
int memory[1002][1002];
int main()
{
    string s1,s2;
    while(cin>>s1>>s2)
    {
        for(int i=1;i<=s1.length();i++)
        {
            for(int j=1;j<=s2.length();j++)
            {
                if (s1[i-1] == s2[j-1])
                    memory[i][j]=memory[i-1][j-1]+1;
                else
                    memory[i][j]=max(memory[i-1][j],memory[i][j-1]);
            }
        }
        cout<<memory[s1.length()][s2.length()]<<'\n';
    }
    return 0;
}

any tips ? thanks in advance

Tags dp, lcs
  • Vote: I like it
  • -18
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Set all array to zero after every test.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    As the 0-th row and 0-th column is always 0 so he don't need to reset the whole array to 0.

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

The problem nowhere says the string will not contain white space character. SO just change — 

while(cin>>s1>>s2) {

to 

while(getline(cin,s1) && getline(cin,s2)){

and get AC :)

→ Reply