### speedy03's blog

By speedy03, 9 years ago,

This is a newbie question. I am confused with transition equations in DP, and always mess them up.

The official solution of this problem looks like:

               // dp[time][number of people]
rep(i, 1, t) rep(j, 1, n)
dp[i+1][j-1] += dp[i][j] * p;
dp[i+1][j] += dp[i][j] * (1-p);


Why it is incorrect (gave me WA) if it is written like this:

dp[i+1][j+1] = dp[i][j]*p + dp[i][j+1]*(1-p)


I have a very vague feeling that dp[i][j+1] may not be updated completely before it is added to dp[i+1][j+1] , but not very sure, since it is supposed to be calculated in previous outer loop already.

How can I treat similar DP problems effectively, and more important, correctly?

• +5

 » 9 years ago, # |   +1 For me, I prefer to update a single state to avoid this problem (and it makes a little more sense to look at). So you don't need to worry about what comes before what. Something like: // dp[time][number of people] for i from 1 .. t for j from 1 .. n dp[i][j] = p * dp[i-1][j-1]; if (j == N) dp[i][j] += dp[i-1][j]; else dp[i][j] += (1 - p) * d[i-1][j]; end end Implementation here