Please help me in this problem : https://leetcode.com/discuss/interview-question/124943/dynamic-programming/125712
People have just given the codes, I want to implement it on my own. Please suggest some approach.
@everule1 @carre @ssjgz
the statement looks incomplete. What time complexity are you expecting? O(s*n) ?
If that’s the case use a simple dp where for each character of the string from left to write you add 1 to the left (or right) position for every non-empty position
Yeah O(s*n) should be fine but how to solve distinct part? Can you tell the states of your dp?
dp[i] is just the number of ways to finish in position i
- initiate dp[i]=0 for all i except i=start; dp[start]=1
- for each character c in s,
- if c=1: do from n-1 to 0: dp[i]=dp[i+1]+1 (only if dp[i+1]>0);
- else: do from 1 to n: dp[i] = dp[i-1]+1 (only if dp[i-1]>0)
the answer is dp[finish]
I think it can be done in \mathcal{O}( (s+n) * log\, n) using a segment tree or bit with range updates