Запись числа как суммы треугольных чисел

Попалась новогодняя задачка - записать число 2018 как сумму разных треугольных чисел
Вообще-то, не так чтобы сложно, на бумажке решить можно, но там было приведено общее количество таких записей. Как их посчитали? Таких чисел, меньших 2018 - аж 63, так что перебором - вряд ли.
Мне все покоя не дает не дающееся мне динамическое программирование - им тут можно как-то добраться до ответа?
Если кто сомневается - это задание не учебное :)

Ответ

Второй раз наталкиваюсь на задачу, которую можно решить длинно, а можно очень быстро... :) Первый ответ опять не убираю, но настоящее решение - в части Update...
Тут недавно спрашивали о переборе с возвратом :) - это почти оно самое. Кстати, с применением рекурсии для упрощения.
Итак, решение может включать некоторое треугольное число, может не включать. В любом случае задача сводится к поиску решений для либо того же числа (если не включаем) или меньшего на включенное треугольное число - но уже для меньшего множества треугольных чисел. Получается рекурсия не глубже 64, но на каждом уровне - ветвящаяся. Но так как отбрасывается очень много вариантов - то посчитать реально, у меня на машине - за примерно 9.5 секунд.
#include #include
using namespace std;
vector tri; // Запас треугольных чисел :) long long total = 0; // Количество решений
vector solution; // Вектор для решения
// Рекурсивный вызов, изначально - доступны все числа (k) void getThree(int n, int k = tri.size()-1) { if (n==0) // Ура, найден! { ++total; // Если захотим вывести - раскомментировать // for(auto i: solution) cout << i << " "; cout << endl; return; }
if (n < 0 || k < 0) return; // Тупик - решение не получилось
// Ветвь с использованием k-го числа solution.push_back(tri[k]); getThree(n-tri[k],k-1); solution.pop_back();
// Ветвь без него getThree(n,k-1); }
int main(int argc, const char * argv[]) { // Заполняем массив треугольными числами for(int i = 1; i <= 64; ++i) tri.push_back(i*(i-1)/2);
// Приступаем... getThree(2018); cout << total << endl; }
На ideone времени не хватает :(
У меня выходит 2693210 вариантов (P.S. так что с long long я явно пожадничал :))
Может, есть какой алгоритм побыстрее - не знаю, но готов поверить :)
Update
Есть и побыстрее, и именно динамическим программированием!
Итак, просто создаем массив
long long res[2019][65];
в котором изначально все элементы - -1, и который указывает количество способов записать число n треугольными числами на выше k-го в ячейке res[n][k]
наша основная формула остается та же, что и ранее -
getThree(n-tri[k],k-1) + getThree(n,k-1)
только теперь мы используем memoization и записываем ответы в массив.
Т.е. функция приобретает вид
long long getThree(int n, int k = tri.size()-1) { if (n < 0 || k < 0) return 0; // Не вышло if (k == 0) // Годится как вариант n==1, так и n==0 { if (n == tri[k]) res[n][k] = 1; if (n == 0) res[n][k] = 1; } else if (n == 0) res[n][k] = 1;
if (res[n][k] == -1) // Если мы еще не рассчитывали это значение - { // считаем и сохраняем res[n][k] = getThree(n-tri[k],k-1) + getThree(n,k-1); } return res[n][k]; }
Такой код позволяет мгновенно получить тот же результат - 2693210.
А вот почему я оставил long long: если позволить выбирать значения повторно (ну, типа, 9 можно писать и как 6+3, и как 3+3+3), то чтобы получить это количество, достаточно просто заменить
getThree(n-tri[k],k-1)
на
getThree(n-tri[k],k)
(т.е. можно использовать то же число повторно). Результат получается тоже весьма быстро, только он куда побольше, так что перебором с отсечением уже не обойтись: 32090936486947985
А неплохая задачка :)