LCS problem

Question

We are given two strings: String 5 of length n and string $T$ of length m for the LC 5 problem, we have produced the following exponential time recursive program.
```
LCM (5, n, T, m)
( if ( }\textrm{n}=0=0||\textrm{m}=0=0) return 0
if (S[n] =m T[m]) result t=1 + LCS (S, n-1, L,m-1);
else result = max (LCS (S, n=1,T,m), LCS (S, n, T,m-1));
return result;
}
```

Then the number of times that LCS (S, 1, T, 1) is recursively called equals $\qquad$

• A. $\binom{n+m-2}{m-1}$
  
• B. $\binom{n+m+1}{m-2}$
  
• C. $\binom{n+m+2}{m}$
  
• D. $\binom{n+m}{m-1}$

Answer 1

option D is correct because if we make the tree of lcs function calling level of Right  sub tree is m level and left  sub tree is n level than total will be (m+n) .. so that (m+n) will be function call  of this program