Как подсчитать допустимые пути в бесконечном корневом дереве («Клен») с определенными ограничениями в Java? ⇐ JAVA

[Anonymous]

Я работаю над проблемой, связанной с уникальной графовой структурой под названием «Клен», которая представляет собой бесконечное корневое дерево с определенными характеристиками:
Структура кленового дерева:< /p>
Каждый узел в дереве имеет ровно n дочерних элементов.
Ребрам, соединяющим узел с его дочерними элементами, присваиваются значения последовательно от 1 до n.
Задание :
Мне нужно посчитать количество путей, которые начинаются с корня этого дерева и имеют общее совокупное значение w.
Кроме того, хотя бы одно ребро в пути должно иметь значение q или более.
Требования к выходным данным:
Результат должен быть предоставлен по модулю (10^9)+7 из-за потенциально большого количества путей.
Ограничения ввода:
Функция принимает три параметра: w, n и q.
Ограничения следующие:

• 1可𝑤,𝑛可1000
• 1可q可n

Ошибка Обработка:
Мне нужно реализовать обработку ошибок для недопустимых входных данных:
Выдать исключение, если w или n меньше 1.
Выдать исключение, если q меньше 1 или больше n.
Проблемы реализации:
Я пытаюсь использовать динамическое программирование для подсчета допустимых путей, но сталкиваюсь с проблемами с логикой. В частности:
Функция иногда возвращает неправильные результаты для определенных тестовых случаев, например:
innovation(3, 3, 2) должна возвращать 1, но в настоящее время возвращает 2.
innovation(28, 6, 3) должен возвращать 110682188, но в настоящее время возвращает 916.
Желаемый результат:
Мне нужна помощь в проверке моего подхода, исправлении любых логических ошибок и обеспечении эффективности и точности решения. Кроме того, я хотел бы подтвердить, что моя реализация обрабатывает крайние случаи и придерживается указанных ограничений.
Я реализовал функцию Java для расчета количества допустимых путей в дереве Maple, как описано в разделе постановка проблемы. Вот что я сделал:
Определение функции: я определил функцию Innovation(int w, int n, int q), которая принимает три параметра, представляющие общее значение путей, количество дочерних элементов на каждый узла и минимальное значение ребра соответственно.
Подход динамического программирования:
Я использовал массив динамического программирования dp для подсчета общего количества путей к каждому возможная сумма до w.
Я инициализировал dp[0] значением 1, так как есть один способ добиться суммы 0 (не взяв ребра).
Я перебрал возможные значения ребер и обновил dp для учета всех возможных путей, которые могут быть сформированы с помощью этих значений ребер.
Расчет допустимых путей:
После расчета общего количества путей я попытался суммировать действительные пути, которые включить хотя бы одно ребро со значением q или более.
Обработка ошибок: я включил проверки ошибок, чтобы генерировать исключения для недопустимых входных значений, как указано.
Ожидаемые результаты:
Я ожидал, что функция точно вычислит количество допустимых путей для различных тестовых случаев, включая:
innovation(3, 3, 2) должна возвращать 3.
innovation(2, 2, 2) должна return 1.
innovation(28, 6, 3) должна возвращать 110682188.
Для входных данных, где w или n меньше 1 или где q находится за пределами диапазона [1, n], я ожидал, что функция для создания исключения IllegalArgumentException.
Наблюдаемые проблемы:
Однако я обнаружил расхождения в выходных данных для приведенных выше тестовых случаев:
Фактический результат для Innovation(3, 3, 2) вместо этого вернул 2 из ожидаемых 3.
Фактический результат для Innovation(28, 6, 3) вернул 916 вместо ожидаемых 110682188.
Я также получил действительные выходные данные для случаев, когда входные данные выходили за пределы определенных ограничений, что подтверждает что обработка ошибок работает должным образом.

Подробнее здесь: https://stackoverflow.com/questions/791 ... cific-cons