A string of digits is given, for example, "12335457". A valid partition is a partition of the string such that each segment is strictly greater than that previous segment. For example, "12  33  54  57" is a valid partition and 57 > 54 > 33 > 12. Another valid partition can be "12  335  457" . How many valid partitions possible for the given string? The maximum length of the string can be 5000. If we use dynamic programming with parameter i and j, which means, the last segment was from i ... to ..j, then we can recurse on the remaining part.
But this approach will take O(n^3) time. How can we reduce it from O(n^3)? asked 27 Jun '18, 16:29

Let dp[i][j] denotes the number of valid partition of string s[1:i] where the last partition ranges from s[j:i] So dp[i][j]=sum(dp[j1][k]) Where $j1k < ij$ i.e. $k>2*j1i$ if(s[j:i]>s[j1(ij)][j1]) dp[i][j]+=dp[j1][j1(ij)] Ohk ,so reasoning, If last segment is of length x,then we can obviously choose previous segment with length less than x . If previous segment is also of same length,then check if last is greater. Now basically u have to find sum(dp[j1][k]) fast So basically when u have calculated dp[i][j] for a given i and all j,u can just calculate suffix[i][j] where suffix[i][j]=sum(suffix[i][j+1]+dp[i][j]) Basically suffix[i][j] will now store sum(dp[i][j] to dp[i][i]) answered 27 Jun '18, 18:07
