Complexity of DFS + DP solution?

DP is O(n^3), three for loops to store information. DFS to find all solution may depend on number of correct breaking candidates we have, where the min is 0, maximum is O(2^n) (for all possible combination numbers). Usually we can assume there will be a constant number of potential breaking given a normal dataset, like <1M possible combination given a string with length <=100.