antivenom's blog

Is permutation and combination in competitive coding is Dynamic programming ?
By antivenom, history, 9 years ago, In English

Hello everyone,I am new to Dynamic programming and what I have observed that in any question whenever I think that this is a permutation combination question,it comes out to be a DP.So my question from you guys is that is permutation and combination Dp in competitive coding.Like this question I thought of P&C but its a Dp

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

»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Combinations and DP are closely related: C(n, k) = C(n - 1, k - 1) + C(n - 1, k).

Usually you only need to think about combinations when you have to optimize from O(n2) to O(n). Then you can use the factorial formula to find C(n, k) in constant time with O(n) precomputation.

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

    So one must be good in Combinations in order to get better fast and furious way in DP ?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      No , combinatorics help only in counting problems while dp can help also in a lot of minimization and maximization problems so there's a lot of kinds of dp that have nothing to do with combinatorics

      → Reply