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
Lets construct a dp array .
dp=0 , dp=2, dp=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 : https://ideone.com/UPBbQQ
Related Problems :
Practice : https://www.codechef.com/problems/BYTES14