jhjfbsbfkbjfnfnfjfj's blog

Help in Combinatorial DP Recurrence Relation
By jhjfbsbfkbjfnfnfjfj, history, 5 years ago, In English

Can anyone tell me how I prove this dp relation of selections of j object from i dp[i][j] = dp[i-1][j-1] + dp[i-1][j] if anyone can explain me the two states in the right hand side of the eqn it would be great. please explain the transitions and states in this problem.

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

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

dp[i][j]=number of ways of choosing j elements out of i elements. First consider any ordering of the elements. Now consider the ith element in this ordering, dp[i][j] can be written as sum of two parts

  1. That contains the ith element, so now you have taken 1 element and you need to take remaining j-1 elements from remaining i-1 elements ie dp[i-1][j-1].

  2. That do not contain ith element so you need to choose all j elements from the remaining i-1 elements ie dp[i-1][j]

→ Reply