### mac_n_cheese_pog's blog

By mac_n_cheese_pog, history, 3 years ago,

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.

• -36

| Write comment?
 » 3 years ago, # |   +3 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.
 » 3 years ago, # |   0 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!
•  » » 3 years ago, # ^ |   0 multiplying makes more sense to me.ive never done combinatorics by adding something
•  » » » 3 years ago, # ^ |   0 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.