[Solved]: Regarding the height of a recursion tree on dynamic programming

Problem Detail: 

I am trying to understand dynamic programming and I am watching this mit video. If you guys could take some time out , can you refer to the slide on 41:36 . Why is the height m+n. I just don't get it why is the heigh of this recurrence tree m+n.

http://videolectures.net/mit6046jf05_leiserson_lec15/

Thank you.

Asked By : user1675999

Answered By : Realz Slaw

Each level you subtract $1$ from the left or the right in the worst case (when $x \ne y$). So intuitively if you go down the left over and over again (along the leftmost part of the tree), it will reach $(1,n)$, at level $m$, and you will only be able to go right from there. Then you will go down $n$ more levels to the bottom.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6276