Проблема в том, что https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/. Мой начальный подход Leetcode был древовидно-рекурсивной проблемой с запоминанием. Проблема может быть охарактеризована тремя параметрами d, f и t. Я решаю проблему определения того, сколько бросков возможно с d кубиками, чтобы бросить цель t, сосредотачиваясь на одном кубике, который может (эффективно) принимать любое значение в диапазоне [1, t]. Мое обоснование в том, что f может быть таким же большим, как t, и нам не нужно учитывать f values> t;следовательно, f = O(t) эффективно.
Таким образом, для каждого n in [1, min(f, t)] я делаю рекурсивный вызов подзадачи, характеризуемой d - 1 die и t - n target, имитирующей один бросок кубика со значением n. В конечном итоге мы достигаем базового варианта d = 1 и можем хранить либо 1, либо 0 в нашей записке с парой <d, t>. Для каждой проблемы мы суммируем решения подзадачи, сохраняем результат в нашей записке и возвращаем его. Это дает нам дерево, подобное следующему:
Итак, мой вопрос: какова временная сложность этого алгоритма?
Понятно, что мы можем касаться максимум каждой комбинации d и t, делая ее Omega(d*t). Однако, поскольку для каждой задачи мы должны суммировать f = O(t) подзадач, я думаю, что мы должны добавить еще один коэффициент t для сложности O(d*t*t) (точнее O(d*min(f, t)*t)). Имеет ли это смысл?
Более того, похоже, это подтверждает восходящее решение, которое работает с таблицей размером d*t, но для каждой задачи необходимо объединить все подзадачи f, что, на мой взгляд,ставит нас на O(d*t*t).