Dynamic Programming State Machine Fundamentals

Algorithms and Data Structures: TheAlgorist.com

System Design: SystemsDesign.Cloud

Low Level Design: LowLevelDesign.io
 Finite state machines are a standard tool to model eventbased control logic.
If a given problem contains different events and depending on which event occurs we can transition from one state to another then it is highly likely that the problem could be solved using Dynamic Programming State Machine approach.To some extent, this approach is quite similar to Decision Making DP Approach. You see which state is giving you the optimal solution (using overlapping substructure property of Dynamic Programming, i.e, reusing already computed result of other state(s) on which the current state is dependent on) and based on that you decide to pick the state you want to be in. Naturally, you will find yourself drawing State Machine diagrams while solving Dynamic Programming problems using this approach. Look at the following problems to have a strong grasp on this approach:
 Stock Trading With Cooldown
 Stock Trading With Transaction Fee
 Max Profit w/ at most 2 Stock Trade Transactions
 Max Profit w/ at most K Stock Trade Transactions
 Max Profit w/ Unlimited Stock Trade Transactions
 Max Profit w/ at most 1 Stock Trade Transaction
From the above problems we will see that the main challenge is to come up with the state machine diagram. Once we have come up with the state machine diagram deriving the Dynamic Programming relations from the state machine is just a piece of cake. State machine diagram naturally gives you the Dynamic Programming relation(s) you need to implement the DP solution.
Instructor:
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
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn