Если мы вычисляем префиксные суммы используя формулу p[i + 1] = s[i] + p[i], является ли это динамическим программированием?
Если мы вычисляем префиксные суммы используя формулу p[i + 1] = s[i] + p[i], является ли это динамическим программированием?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | Radewoosh | 3415 |
| 8 | Um_nik | 3376 |
| 9 | maroonrk | 3361 |
| 10 | XVIII | 3345 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 141 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
Да.
там в тегах в том числе обычно указано дп у задач на префсуммы
Да, это динамическое программирование, так как ты решил задачу благодаря тому, что разбил её на более простую, т.е. взял меньшее i. Однако это достаточно частный случай, так как вся прелесть динамического программирования заключается именно в том, что ты можешь разбить задачу на несколько более простых, не только на одну.