Question

I want to understand the dynamic programming equation of https://en.wikipedia.org/wiki/Bertrand%27s_ballot_theorem theorem. it is this

If i number of people voted for A and j number of people voted for B then dp[i][j] counts the number of ways voting can happen.

dp[ i ] [ j ] = dp[ i ] [ j - 1 ] + dp[ i - 1 ] [ j ] .

basically, I want to find the number of ways candidate A is in the winning position throughout. Can anyone explain the logic behind the dp equation ? I think it works like this. We have a sequence of A and B.In which A wins throughout. Now we add one more A to that sequence or add one more B to it.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top