Problem Description :
A man is " n " distance away from the home . He needs to reach his home given that he can either 2 or 3 places backwards with the probability " p " for jumping 2 steps backwards and " 1-p " for jumping 3 steps backwards .
Assuming each jump takes 2 sec find the expected time to reach his home .
Problem Type : Medium / DP + Probability
Explanation :
Lets construct a dp array .
dp[0]=0 , dp[1]=2, dp[2]=2 are the base conditions as each jump takes 2 sec.
No we run a loop fom 3 to n and for each state we have the following relation :
dp[i] = (dp[i-2]+2)p + (dp[i-3]+2)(1-p) as we can go 2 steps backward with probability p and 3 jumps backwards with probability 1-p .
Final answer will be dp[n].
Complexity : O(t*n) where " t " is the number of test cases .
Solution : UPBbQQ - Online C++0x Compiler & Debugging Tool - Ideone.com
Related Problems :
Practice : BYTES14 Problem - CodeChef
Contest : CodeChef: Practical coding for everyone