Как мне решить эту проблему динамического программирования?

Question

Я использую язык C ++.

У Марка "N" дней.Первоначально он находится в положении (h1,0) на оси X.Каждый день он может переходить к координатам (h1 + a, 0) или (h1 + b, 0) или (h1 + c, 0).Он может выбрать любой, какой захочет.Каждый день он может ходить в (+ a, + b или + c).В N-й день он должен достичь позиции (h2,0).Подсчитайте количество способов, которыми Марк может достичь (h2,0) за N дней.

Значения N, h1, h2, a, b, c являются большими (координаты и значения a, b, c также может быть отрицательным, в некоторых случаях a = b или b = c или c = a или a = b = c)

Мой подход таков: - Каждый день я сохраняю позиции, которые онможет достичь в этот день с количеством (количество способов), чтобы достичь этой позиции.Я использую карту, чтобы сделать это.И этот подход не эффективен.

Может кто-нибудь поделиться более эффективным подходом?

Мой второй подход, который должен сработать, - это изменение проблемы обмена монет: -)

Пример: -

N = 3, h1 = 0, h2 = 6, a = 1, b = 2, c = 3

Ответ: -7 (количество способов)

1-й путь :-( 1 + 2 + 3)

2-й способ :-( 1 + 3 + 2)

3-й путь :-( 2 + 1 + 3)

4-й путь :-( 2 + 3 + 1)

5-й способ :-( 3 + 1 + 2)

6-й способ :-( 3 + 2 + 1)

7-й способ :-( 2 + 2 + 2)

Формат :-( Выбор на 1-й день + Выбор на 2-й день + Выбор на 3-й день)

Ограничения: - 1 <= N <= 10 ^ 5. </p>

-10 ^ 9<= h1, h2, a, b, c <= 10 ^ 9.</p>

Answer 1

Если вы знаете, сколько раз использовали a, b, c, то вы можете легко сказать результат.

Например, если мы используем x раз a, y раз b и z раз c дляполучить h2 из h1, мы можем сказать, что способ использования x раз a, y времен b и z времен c равен

факториал (x + y + z) / (факториал (x) *factorial (y) * factorial (z))

.

Теперь, как мы можем узнать значения x, y, z.Может быть много триплетов x, y, z.

Теперь мы можем считать от 0 до n каждого числа как x.

Так что для каждого x от 0 до n,

x a + y b + z * c = (h2-h1)
y + z = nx

Как мы знаем значенияx, a, b, c, h2, h1
мы можем переписать уравнение,

y b + z c = (h2-h1-x a)
y b + z c = k, где k = (h2-h1-x a)

Теперь решите задачу для следующегоуравнения:

y b + z c = k
y + z = nx

Так что может быть решение или нет для этогоуравнение такое, что y и z являются целыми числами.

Если есть решение, то эти уравнения будут разрешимы.

После нахождения y и z мы можем вычислить перестановку для x, используя

факториал (x + y + z) / (факториал (x) * факториал (y) * факториал (z))

.

Итакесли нет никакого решения, то вы должны пропустить текущий x.
Таким образом, вычислите y и z для каждогох от 0 до п и сложить их.