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
- Optimal Structure
- Recursive Implementation
- Memoized / Bottom up Version
- Complete Solution
Here is the code :