Recently, I learnt about DP and started solving problems related to it. When I know the problem is on DP and then when I solve the question, I am surely able to find the recurrence relation, but when not specified, I am finding it difficult to identify whether the problem is on DP or not. How to distinguish whether a problem is on DP or greedy or ad hoc? And can somebody also provide links of good problems involving DP.
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 3757 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | maomao90 | 171 |
| 2 | awoo | 165 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | maroonrk | 155 |
| 6 | nor | 154 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Jun/02/2024 12:56:00 (i2).
Desktop version, switch to mobile version.
Supported by
Auto comment: topic has been updated by code_kika (previous revision, new revision, compare).
Like in all other problems you should try different approaches. You said that if you know that the problem is DP then it is easy for you to solve (probably you haven't seen really hard DP problems). Try to assume that problem is DP. If you can figure out the solution in 10 minutes (or 15, or whatever) then... you solved the problem, great. If you cannot then maybe it is not DP? You cannot be sure but it is better to try something else.
Knowing some famous DP problems might be helpful. If you see a knapsack problem with some additional constraints then the solution is probably like in a knapsack problem.