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.
# | User | Rating |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 155 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | nor | 152 |
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.
Name |
---|
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.
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!
multiplying makes more sense to me.ive never done combinatorics by adding something
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.