Daily Archives

One Article

Rod Cutting Problem Implementation in c++


I am practicing Dynamic Programming problems from my textbook Cormen ,I though it would be a great idea to post its implementation code in c++ .

If anyone needs any help regarding it shoot me an email or leave a comment .

Few Observations :

Translating psudocode from cormen to c++ is not that simple , you might underestimate the complexity involved in for example I had a lot of trouble with array indexes, But I finally solved it by drawing a rough recursion tree on my white board .

I was earlier scared looking at the nested and complex structure of bottom – up algo , memoized version seemed so straightforward but when I drew recursion tree and coded the solution , the intuition behind the code became perfectly clear

I have observed that dynamic programming implementation from scratch involves quite a few steps (4 typically ) , So to make things simple and self motivation I have created a 4 items checklist , everytime Isolve any dynamic problem I make sure I follow checklist of items / steps in chronological order .

4 steps are obviously

  1. Optimal Structure
  2.  Recursive Implementation
  3. Memoized / Bottom up Version
  4. Complete Solution

Here is the code :