speedy03's blog

DP in Ilya and Escalator (#293 Div 2 D)
By speedy03, 10 years ago, In English

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?

Tags dp
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply