##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
When naive DP times out
Some DP transitions look like this: . You need the minimum over the last states. The naive approach checks all candidates for each , giving you time.
When and , that's a billion operations. Your code times out. You need a way to track the minimum without rechecking all candidates every time. What if you could maintain a "shortlist" of candidates that might become optimal?
