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

Материал из Algocode wiki
Версия от 09:10, 20 марта 2020; Глеб (обсуждение | вклад) (Новая страница: «==Облегчение== Решим сначала задачу найти количество чисел < $10^k$ с суммой $S$, пусть dp[i][j] - к...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Облегчение

Решим сначала задачу найти количество чисел < $10^k$ с суммой $S$, пусть dp[i][j] - количество чисел из i разрядов с суммой j, тогда ответ - dp[k][s], формула пересчета же следующая $dp[i + 1][j + c] += dp[i][j] \forall c in [0, 9]$

Возвращение

Заметим, что единственное, что теперь меняется, это то что нам нужно знать меньше ли то число которое мы набрали нашего $k$ или нет, давайте, тогда изменим нашу динамику на $dp[i][s][can]$ - мы набрали первые i цифр числа, с суммой s и при этом can = 1, если мы уже меньше числа $k$ и 0 иначе, тогда база - dp[0][0][0] = 1, пусть $k_{i}$ - i-ая цифра с начала числа $k$, формула перехода $dp[i][j][0] = \sum\limits_{c = 0}^{c <= k_{i - 1}} dp[i - 1][j - c][0], dp[i][j][1] = \sum\limits_{c = 0}^{c < k_{i - 1}} dp[i - 1][j - c][0] + \sum\limits_{c = 0}^{c <= 9} dp[i - 1][j - c][1]$, ответ - dp[len(k)][s][1] + dp[len(k)][s][0].



Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin