Usu's blog

Dynamic programming and combinatorics
By Usu, history, 7 years ago, In English

Hey guys, recently I started to deepen algorithmic science. I relised that dynamics include a huge amount of techniques and approaches, I know some of them, but I'm not good at dinamycs with bits/masks for example. I don't know also many things in combinatorics like "the number of sequences such that their sum is t" which is 2^(t-1), not really this, but combinatorics like this. So I'm asking you for help. Can you give me please some useful links or name of methods? I would be greatful.

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

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

For DP on bitmasks, it really is just DP on sets, so it might be more intuitive to work out the DP recurrence on sets and convert to bitmasks later. To get good there is no other way than practice.

For counting combinatorics honestly Wikipedia articles are pretty decent. Read the pages binomial coefficients and Catalan numbers for starters. Once you start to understand how they work many of their common applications will seem "obvious".

→ Reply