• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.



In many Dynamic Programming problems (i.e, problems which show (1) overlapping subproblems, and (2) optimal substructures properties) you would see that for a given situation you would have multiple options for actions you can take. Often times this would involve taking decision whether to use (INCLUDE) or not to use (EXCLUDE) the current state. So, the problem would require you to make a decision at a current state, so that you can get optimal solution for the current state.
More generally, this approach can be summarized as

  • If you decide to choose the current value, use the from the already computed results (Optimal Substructure) where the value was ignored.
  • If you decide to ignore the current value, use from already computed results (Optimal Substructure) where the value was used.


The chapter House Robber beautifully demonstrates this approach.



The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave