Наблюдение, касающееся динамического программирования, которое все, скорее всего, уже давно сделали.
Вместо того чтобы строить массив вида 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
Лично я не понял, каким образом таки Вы ужали многомерность.
Помимо этого очень много задач динамического программирования могут быть оптимизированы разными способами (монотонность точки разреза, CHT), которые прямо зависят от того, в каком порядке производятся вычисления, что иногда можно поменять какие-нибудь циклы местами и какой-нибудь из подходов станет применимым, хотя не был ранее. Рекурсивная дп хороша для описания решения, действительно она нередко короче итеративной (хотя далеко не всегда), и обычно понятнее, но я всё равно буду придерживаться итеративной, из-за быстродействия и потенциальных оптимизаций
Первоначально в голову приходит состояние
dp[i] [j] [difference], где difference равно разности между красными и черными картами. И когда я начинаю думать в терминах такогоdpв итеративном варианте, я запутываюсь в рассуждениях, не вижу как делать переходы, хотя тут конечно тоже можно убрать третий параметр и в итеративном варианте. Получается, что тому, кто имеет уже опыт решения графовых задач, может быть очень полезным решать рекурсивно (если цель именно решить, сдать задачу) , потому что в голове уже есть необходимый отлаженный механизм мышления.В качестве другого примера на ум приходит: http://acm.timus.ru/problem.aspx?space=1&num=1437
Здесь мой первый порыв -- это написать динамику по трём измерениям
dp[x] [y] [z], равную искомому количеству способов отмерить различные объемы топлива, где x, y, z -- объемы данных канистр.Я провёл некоторое время в безуспешных попытках получить формулу для такой динамики.
Стоило мне начать думать в терминах графа, где вершина содержит текущее количество топливо в каждой канистре, как сразу стало понятно, что достаточно найти количество вершин достижимых из начального состояния, имеющих различную сумму
s=x+y+zпараметров.То есть фактически этот метод просто помог мне преодолеть инертность мозга.
Так там нужно не количество способов, а true/false. Поэтому ты и не придумал формулу. Не ту задачу решал.
По сути ведь это получается просто перебор с запоминанием (memoization)? Если да, то это, на самом деле, довольно хороший способ придумывать динамику, имхо.