Dynamic Programming State Machine Fundamentals
Get started
জয় শ্রী রাম
🕉- Finite state machines are a standard tool to model event-based 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.
