Блог пользователя MonsieurV

I have a dynamic programming problem but I can't think of a way to do it
Автор MonsieurV, история, 5 лет назад, По-английски

There are M gifts and N students. Count the dividing numbers so that the number of gifts from the following student is not greater than the amount of the previous student's gift

input 3 2 output 2

explain : There are 2 ways to choose : (3;0) and (2;1)

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
5 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

dp[N][M] = dp[N-1][M — M//N ] + dp[N-1][ M — M//N + 1] + ... dp[N-1][M] — every student can have i gifts (from max M//N to min 0) and for every i (number of gifts) you should add all combinations of N-1 students rearranging M-i gifts.

or shorter: dp[N][i] = dp[N][i-1]+dp[N-1][i-1] — O(MxN) dificulty.

→ Ответить