Summary
In this category, given a range alg[i,j], the subproblem is not self contained. To make the subproblem independent to outer ranges, some extra states need to be added.
DP in Intervals (Extra States)
Posted on
LeBlanc’s law: "Later equals never".
In this category, given a range alg[i,j], the subproblem is not self contained. To make the subproblem independent to outer ranges, some extra states need to be added.