State Machine DP
Model holding, sold and resting as states and write the transitions between them per day.
Dynamic ProgrammingO(n * k)New4 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
buy and sell stock with k transactions
cooldown
transaction fee
The template
Get this into muscle memory, then adapt the condition per problem.
let hold = -Infinity, sold = 0, rest = 0;
for (const p of prices) {
const prevSold = sold;
sold = hold + p;
hold = Math.max(hold, rest - p);
rest = Math.max(rest, prevSold);
}If you are stuck
The generic hint ladder for this pattern, in order.
- 1At any day you are in one of a few situations. Name them.
- 2Write what each state can become tomorrow.
- 3Transaction limits become another dimension of the state.
Drill it
Every problem in the bank that uses this pattern.
0 / 4 solved