Some time ago someone told me that when your choices are quite dependent to each other then using dp will be a great idea having this in mind it helped me to come up with the dp idea in a lot of problems in the first place.Yesterday I saw a problem that had dp solution see the link .I wasn't able to recognize it is a dp problem until the end of the contest.But a yellow coder seeing the problem in the first place told that it is a standard dp problem.So my question is how to recognize "Standard dp" problems?Can anyone tell me what property of the problem makes it a standard dp problem?Thanks in advance.
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 08.11.2026 21:20:45 (g2).
Десктопная версия, переключиться на мобильную.
При поддержке
I think that: A property of a standard dp problem is such the problem that is a simple, well-known, well-discussed problem that can be solved with dynamic programming and having a lot of research, tutorial videos, papers about it as its wonderful applications. So it can be recognized when we observed many problems solved have the same pattern of a simpler standard dp problem.
having a lot of research, documentaries, papers about it as its wonderful applicationsI'd love to watch some dp documentaries
:VVvvv oops, sorry for my poor English, edited to
tutorial videosresearch and documentaries!! , bros in the military lol
$$$n \leq 100$$$ and $$$a_{i} \leq 100$$$ suggests dp. Looks too big for bitmasks and meet in the middle and too small for most other standard cp techniques.
there are a multitude of questions with large $$$N$$$ that are still solvable with DP. it's more about whether you can turn the question into states or subproblems.
Coding problems asked in company interview's are "standard dp".
On a serious note: Dimension is the only way i recognise dp.
Even i had the same question in my mind . I am mostly accustomed to solving dp problem that are standard and you can figure the dp states from the question itself. But this is different type of dp problem. Hope to solve more of such problems .
Standard problems are recognized by having experience. Looking at constraints and forcing DP is dumb.