What i was thinking was d[i][j] denote number of sequence of length i if i put element j at this position
recurrence can be made with the help of the string values if s[i-1] = < then if i am trying to put j element then my ans will dp[i-1][1] .+ … dp[i-1][j-1] (can be calculate using prefix sums)
if it is > then my dp[i][j] will be dp[i-1][j+1] + dp[i-1][j+2]… dp[i-1][n] (again prefix sums)
but i am not getting correct answer even in sample test case
Please correct me if i am wrong and help me to solve the problem
1 Like