Abinash's blog

LightOJ 1013 Love Calculator DP Problem

By Abinash, 10 years ago, In English

You are developing a 'Love calculator'. So, given two names your software will generate the percentage of their 'love' according to their names. The software requires the following things: 1.The length of the shortest string that contains the names as subsequence. 2.Total number of unique shortest strings which contain the names as subsequence. Now your task is to find these parts.

I find 1st part by computing (length of 1st name +length of 2nd name — LCS(1st name , 2nd name ).

But how to find 2nd part ??

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

We know unique string length from s1.length+s2.length — LCS(s1,s2)=L. Lets define the DP states , one states will be unique string length (L) , another two will be s1.length(a) and s2.length(b). The recurrence will be ... 1.We take a letter from first string means solve(l-1,a-1,b). 2. We take a letter from second string means solve(l-1,a,b-1). 3. If letter from first string and second string same that means solve(l-1,a-1,b-1) cause if we take from both string will not unique. Now come some condition... 1. If letter from first string and second string same that means , we have only one way . solve(l-1,a-1,b-1). 2. If letter from first string and second string different that means we have two way solve(l-1,a-1,b) and solve(l-1,a,b-1) . 3. If any a=0 then we must have take letter from second string means solve(l-1,a,b-1) . 4. If any b=0 then we must have take letter from first string means solve(l-1,a-1,b).

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

first, calculate LCS, all states by d[n][m]

build dynamic on this states :

dp[i][j] :

  1. s[i] == t[j] -> dp[i + 1][j + 1] += dp[i][j]

else

  1. d[i][j + 1] + 1 == d[i + 1][j + 1] -> dp[i + 1][j + 1] += dp[i][j + 1]

  2. d[i + 1][j] + 1 == d[i + 1][j + 1] -> dp[i + 1][j + 1] += dp[i][j + 1]

that means, if we came from 2 states we need to add both

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

The main problem of this problem is to understand the problem well. :P

There's 2 parts of this problem.

  1. Finding the shortest length of the string that contains the both name as sub-sequences.
  2. Finding the number of unique shortest string that contains the both name as sub-sequences.

For the 1st part answer is — ans=a.size() + b.size() — lcs(0,0);

For the 2nd part find the lcs string. If a[i]==b[j] go to call(i+1,j+1) else check which one is greater between lcs(i+1,j) and lcs(i,j+1). If lcs(i+1,j) is greater go to call(i+1,j), if lcs(i,j+1) is greater go to call(i,j+1) and if both are equal, then call(i+1,j)+cal(i,j+1).

Base Case: when you reach at the end of any string return 1;

Critical Case: when you are finding lcs(0,0) do memoization even for the base case. I mean if i==a.size() return dp[i][j]=0;

→ Reply