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 | 3947 |

2 | ecnerwala | 3654 |

3 | jiangly | 3627 |

4 | jqdai0815 | 3620 |

5 | orzdevinwang | 3612 |

6 | Benq | 3586 |

7 | Radewoosh | 3582 |

8 | Geothermal | 3569 |

8 | cnnfls_csy | 3569 |

10 | ksun48 | 3474 |

# | User | Contrib. |
---|---|---|

1 | awoo | 163 |

2 | maomao90 | 160 |

3 | adamant | 156 |

4 | atcoder_official | 155 |

5 | maroonrk | 152 |

6 | -is-this-fft- | 148 |

6 | SecondThread | 148 |

8 | Petr | 147 |

9 | nor | 145 |

10 | cry | 144 |

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.

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/06/2024 13:12:59 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

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.