DP-задачи часто удобнее решать как графовые задачи

Revision ru1, by Mahilewets, 2017-07-14 09:33:12

Наблюдение, касающееся динамического программирования, которое все, скорее всего, уже давно сделали.

Вместо того чтобы строить массив вида DP[dim_1][dim_2][dim_3]...[dim_N], часто бывает более удобно и понятно строить явным образом граф вида vector <struct {int state_1, state_2, state_3, ..., state_N;} >.

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

Тогда, например, можно не использовать громоздкие конструкции, чтобы инициализировать значения по умолчанию, а просто воспользоваться значениями для полей структуры по умолчанию.

Также это позволяет обойтись вообще без написания циклов в явном виде, всё можно сделать при помощи рекурсивной функции обхода графа.

Таким образом можно добиться даже экономии памяти, если создавать новое состояние непосредственно перед тем, как обход графа собирается пойти в него.

Пример, где такой подход позволил избежать громоздких выкладок с многомерным массивом:

http://acm.timus.ru/problem.aspx?space=1&num=1501 http://ideone.com/tm1TcB

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru1 Russian Mahilewets 2017-07-14 09:33:12 1117 Первая редакция (опубликовано)