We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

I decided to read the discussion page before solving the actual problem since I can't believe what I see.

The most interesting part is not that you have to solve the LCS problem which is, by the way, much more complicated than dynamic casts in C++. The real fun begins when you realize that the only thing that you can edit is the body of a single function!

This means that you can't use recursion solving the LCS! You must unroll the structure of the problem "by hand" using some array, as it was shown below. I tried some tricks with local lambdas or std::function which didn't work, especially that I cannot include the header "functional". But maybe I didn't try hard enough :)

see CLRS intro to algorithms 3ed chapter 15, which discusses the two types of DP approaches: top down recursive, and bottom up iterative. The bottom-up approach builds a table starting from the simplest solutions, and that's the approach that is necessary here.

the recursive relation for LCS can naturally be translated to an iterative non-recursive algorithm for successively filling up the memo table of subproblem answers. That can be done with a simple C-style double nested for loop, and doesn't require defining external functions or fancy lambdas / functors.

## Magic Spells

You are viewing a single comment's thread. Return to all comments →

I decided to read the discussion page before solving the actual problem since I can't believe what I see.

The most interesting part is not that you have to solve the LCS problem which is, by the way, much more complicated than dynamic casts in C++. The real fun begins when you realize that the only thing that you can edit is the body of a single function!

This means that you can't use recursion solving the LCS! You must unroll the structure of the problem "by hand" using some array, as it was shown below. I tried some tricks with local lambdas or std::function which didn't work, especially that I cannot include the header "functional". But maybe I didn't try hard enough :)

This is just crazy...

Exactly! i had never solved LCS non recursively. Quite interesting.

see CLRS intro to algorithms 3ed chapter 15, which discusses the two types of DP approaches: top down recursive, and bottom up iterative. The bottom-up approach builds a table starting from the simplest solutions, and that's the approach that is necessary here.

the recursive relation for LCS can naturally be translated to an iterative non-recursive algorithm for successively filling up the memo table of subproblem answers. That can be done with a simple C-style double nested for loop, and doesn't require defining external functions or fancy lambdas / functors.

You can use a local struct type to define a local function within a function: