Блог пользователя KingMace

Автор KingMace, история, 3 года назад, По-русски

Если мы вычисляем префиксные суммы используя формулу p[i + 1] = s[i] + p[i], является ли это динамическим программированием?

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Да.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    там в тегах в том числе обычно указано дп у задач на префсуммы

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Да, это динамическое программирование, так как ты решил задачу благодаря тому, что разбил её на более простую, т.е. взял меньшее i. Однако это достаточно частный случай, так как вся прелесть динамического программирования заключается именно в том, что ты можешь разбить задачу на несколько более простых, не только на одну.