Substring DP

If the subproblem cannot be expressed as a prefix or suffix, then defining the subproblem by substring (interval) might be the way to go.

Defining State The state is an interval. i.e. DP[i][j] represents the optimal score for s.substring(i,j+1) or s[i:j+1].

Solve by Substring We normally have no idea which item to process last in order to optimize the problem. As any DP problem, at the current stage, we will not be able to determine one optimal choice. So instead, we have to try all possible choices (partitions) at that stage.

Topological Order Prefix normally goes from left to right. Suffix normally goes from righ to left. They all follow the increasing substring size (to satisfy all dependencies). So does substring.

Time Complexity Enumerating all substrings takes O(n^2) and partitioning at each stage takes O(n). Therefore, normally O(n^3).