Динамическое программирование.

Динамическое программирование очень важная составляющая ACM и программирования в целом. Если так подумать тот же алгоритм дейкстры использует эту идею. Тут хотел много порассуждать об этом, но смысл статьи в другом, а именно постараться объяснить что это за штука и помочь начинающим научиться видеть решения с ДП, поэтому опущу эту часть в целях экономии времени.

Основная идея ДП это оптимизация перебора. Сводим задачу к полному перебору всех вариантов, а затем отсекаем те варианты, которые в ходе этого перебора решаются повторно. Статью я решил по-быстрому запилить после ответа на вопрос в теме. Рассмотрим задачу которую пытается решить автор сего поста. Ответьте на вопрос какова сумма цифр всех чисел в интервале от A до B, обозначим это как Q(A, B). (A, B <= 10^9) В таких задачах часто используется такой прием: научимся отвечать на Q(0, X) а затем вычислим Q(A, B) как Q(0, B) — Q(0, A — 1). Ок, обозначим Q(0, X) как F(X). a[i] — i-тая цифра числа X, т.е. X = a[0] + a[1] * 10 + a[2] * 100 и т.д.

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

int a[MaxDigits];
int x[MaxDigits];

int BuildNumberFromDigits(int* a); // собрать число из цикверок, описана где-то в другом месте программы

int Ans(int pos, int sumOfDigits) {
    if (pos == MaxDigits) {
        if (BuildNumberFromDigits(x) <= BuildNumberFromDigits(a))
            return sumOfDigits;
        else
            return 0;
    }
    int res = 0;
    for (int digit = 0; digit < 10; ++digit) {
        x[pos] = digit;
        res += Ans(pos + 1, sumOfDigits + digit);
    }
    return res;
}

тупейший перебор всех вариантов чисел из MaxDigits цифр. ну не совсем тупейший, сумму цифр я считаю на ходу, а не в конце рекурсии, но думаю эту незначительную оптимизацию может сделать и ваша бабушка.

Помедитируем на этот код и подумаем как можно сократить перебор вариантов, какие подзадачи решаются по многу раз, что еще можно соптимизировать? ну первое что бросается мне в глаза это то, что сравнение итоговых чисел if (BuildNumberFromDigits(x) <= BuildNumberFromDigits(a)) можно делать также по ходу рекурсии. давайте заведем некоторый сравнятор чисел, который выполняет сравнение чисел узнавая цифры по одной начиная со младших разрядов. удобнее конечно написать такой онлайн сравнятор, который узнаёт циферки в порядке от старших к младшим, и здесь можно изменить порядок перебора, но это не принципиально. Главное у нас есть некоторая фиговина, которой одна за одной даются циферки числа x а затем мы можем узнать результат сравнения числа X и того числа чьи циферки мы давали.

пример:

TComparer cmp(X);
cmp.AddDigit(1);
cmp.AddDigit(2);
cmp.AddDigit(3);

bool LessOrEqual = cnt.IsLessOrEqual(); // bool LessOrEqual = (123 <= X);

после внедрения этой штуки в рекурсию она примет вид:

int Ans(int pos, int sumOfDigits, TComparer cmp) {
    if (pos == MaxDigits) {
        return cmp.IsLessOrEqual();
    }
    int res = 0;
    for (int digit = 0; digit < 10; ++digit) {
        TComparer cmp2 = cmp;
        cmp2.AddDigit(digit);
		res += Ans(pos + 1, sumOfDigits + digit, cmp2);
    }
    return res;
}

TComparer cmp;
cmp.Init(a);

int ans = Ans(0, 0, cmp);

Давайте я покажу вам немного уличной магии. Заметим, что сравнятор имеет довольно небольшое число состояний. Это позволяет нам применить запоминание. (англ Memoisation, а не MemoRisation, как часто ошибочно пишут русскоязычные программисты.) Запоминание работает так: заходим в рекурсию, проверяем не вызывали ли мы ранее функцию с такими же точно параметрами? Если вызывали, то возвращаем запомненный ранее результат, иначе вычисляем его, и перед возвратом запоминаем то, что мы посчитали.

map<TComparer, int> dp[10][100];

int Ans(int pos, int sumOfDigits, TComparer cmp) {
    if (dp[pos][sumOfDigits].find(cmp) != dp[pos][sumOfDigits].end())
        return dp[pos][sumOfDigits][cmp];
    int res = 0;
    if (pos == MaxDigits) {
        res = cmp.IsLessOrEqual();
        dp[pos][sumOfDigits][cmp] = res;
        return res;
    }
    for (int digit = 0; digit < 10; ++digit) {
        TComparer cmp2 = cmp;
        cmp2.AddDigit(digit);
		res += Ans(pos + 1, sumOfDigits + digit, cmp2);
    }
    dp[pos][sumOfDigits][cmp] = res;
    return res;
}

В такой манере можно написать любую задачу на ДП.

Общий вид решения такой:
1) перебираем все варианты рекурсивно
2) в качестве одного из аргументов рекурсивной функции передаем состояние перебираемого объекта
3) применяем запоминание.
4) ???????
5) PROFIT!

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

заметим, что изначальную оптимизацию Q(A, B) == Q(0, B) — Q(0, A — 1) можно было не придумывать, просто состоянием перебора была бы пара "сравняторов".

В качестве примера из жизни вспоминается случай, когда применение этого подхода стало единственным моим шансом на то чтобы сдать задачу. Задача была из этой же области — "теории цифр" — задачи на подсчет количества чисел (и/или сумму цифр), у которых на цифры наложены некоторые условия. Не помню формулировки, но в ограничениях на цифры были использованы массивы цифр чисел, и перевёрнутые массивы цифр. перебираемых чисел было два, и перебор приходилось осуществлять двигаясь сразу с обеих сторон. т.е. я перебирал четыре циферки ставил одну слева и одну справа у каждого из чисел и шел вглубь перебора, ближе к середине чисел. Подумав над задачей, я увидел что как-то так можно решить задачу, но написать такой вот "сравнятор", или точнее конечный автомат который что-то вычисляет, оказалось самой сложной подзадачей. Конечный автомат оказался невероятной извращенности штуковиной. Он вроде бы складывал эти два числа онлайн, цифра за цифрой в этом тупом порядке. Там были какие-то флаги переноса и займа, позиции, и вообще не пойми что. Когда я наконец получил плюс по этой задаче мне вспомнился тот самый негр в фуражке. Потому что это одно из самых извращенных решений мною написанных, при этом сама рекурсия заняла всего десяток строк, менее пяти процентов кода.

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

PS: "Остерегайтесь багов в коде выше, я только доказал что он корректен, но не тестировал его"(c) Дональд Кнут