Solution1:
My DP solution. DPB[i]=true means substring s.substr(0,i) is breakable. so the solution is to find DPB[len].
dp[i] has the boolean value that means if string[i : n] can be partitioned according to our dictionary. Hence dp[len] represents the empty string and dp[0] is the answer we are looking for.
For each iteration in the inner for loop, we add a new cut at index j to string[i : n], in whcih string[i : j] has never checked before but string[j + 1 : n](result is in dp[j + 1]) has been known since the previous iteration in outer loop.
No comments:
Post a Comment