MonsieurV's blog

I have a dynamic programming problem but I can't think of a way to do it
By MonsieurV, history, 5 years ago, In English

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)

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i was tried with dp[N][i] = dp[N][i-1]+dp[N-1][i-1] but it wrong

    → Reply