mac_n_cheese_pog's blog

why is dp so strange
By mac_n_cheese_pog, history, 3 years ago, In English

dp problems r combinatorics.i dont know why people dont use some kind of permutation and combination formula.idk how adding some random states like dp[i]=dp[i-1] bla bla bla works.pretty dumb concept if u ask me.

  • Vote: I like it
  • -36
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Only trivial dp problems can be solved with combinatorics formulas. If the question is "how many distinct paths are there on a nxm grid from the bottom left to top right corner going only up and to the right", you can solve it with combinatorics. But add much else (e.g. some of the squares of the grid can be blocked) and suddenly combinatorics isn't going to be helpful.

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

Direct permutation and combination formulas aren't going to work for more complex problems.

And we don't add random states. Its like if you are talking about this expression "dp[i]+=dp[i-1]", then it solely means that the ith state is dependent only on (i-1)th one.

Like for a sample question, the dp[i] might mean the number of ways of climbing i stairs if you can take only steps of unit lenght (which is obviously 1 as 1->2->3...->i).

But more precisely through dp, you can understand that to reach the ith step you need to know the number of ways to reach (i-1)th step * 1 (that is the final element should be fixed to i, so multiplied by only 1). Thats it. Nothing dumb neither random!

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

    multiplying makes more sense to me.ive never done combinatorics by adding something

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

      In a way you are multiplying. So it will sense once you try to understand, else you will keep on complaining about it and will never learn.

      → Reply