I am not able to understand under the heading “Another Easy Solution” DP.
Pseudo Code is not working for me but using the idea I solved the problem.
So i change the code for moving from position 0 to n-1 .(rather than from 1 to n).
I’ve used a solution similar to the one by Sergey Nagin.
I have, however, used 10 iterations instead of 20. I got AC which could be due to weak test cases.
Can someone please give a test case that shows the possible mistake in my code?
Or is it actually possible to do it in 10 and not 20 iterations?
The following arrays in my code have the following meaning as in the pseudo code by Sergin.
val[i] - dp[i] (stores minimum no of moves to reach this point)
minval[i] - Q[i] (stores minimum no of moves to reach the number i)
I have applied the same logic as given in the Optimized BFS solution and I have tested my program for all the test cases, including the ones given in the comments above. Still it gives wrong answer.
Well, my line of reasoning for “Another easy solution” was different.
Think in terms of forward jump and backward jump.
If there is only forward jumps , then
for(i=1;i<len;++i)
{
dp[i] = Min(dp[i-1]+1 ,min[str[i]-'0']+1);//min[] equivalent to Q[] in editorial
min[str[i]-'0']=Min(min[str[i]-'0'],dp[i]);
}
is enough to find dp[n-1].
If there is only one backward jump in the final answer , then we need to run the above code , one more time now considering , dp[i+1]+1 also, i.e.
I thought of modelling the problem into graph and then doing a simple bfs to get the correct number of jumps .I tried modelling the problem into graph and since the indices with same character has also an edge, it takes me O(n^2) to model these edges.This gives me TLE. Help me to tackle this problem.
I thought of modelling the problem into graph and then doing a simple bfs to get the correct number of jumps .I tried modelling the problem into graph and since the indices with same character has also an edge, it takes me O(n^2) to model these edges.This gives me TLE. Help me to tackle this problem.