Возможно, существует возможность анализировать его аналитически и придумать решение O (1). Тем не менее, это займет кого-то гораздо умнее, чем я, чтобы понять :) Вот решение динамического программирования.
Я принимаю за это решение, что все значения должны быть положительными. Кроме того, я предполагаю, что все значения в последовательности должны быть неравными с предыдущим значением. Оба эти условия, по-видимому, подразумеваются, но в явном виде не сформулированы.
Во-первых, давайте немного изменить эту проблему таким образом, что, в дополнение к N, M, K и L, мы также присваивают значение последнего члена в последовательности применяется п. Давайте также добавим еще одну переменнуюI, которая представляет, является ли последний член частью увеличивающейся или уменьшающейся последовательности. Затем мы определим функцию F, чтобы вернуть число возможных последовательностей, заданных , всех этих значений.
N = number of values in sequence
M = number of "runs" in the sequence
K = max value allowed
L = max difference between adjacent sequence terms
I = whether the last term is increasing or decreasing
an = last term in the sequence
FK,L(N,M,I,an) = number of possible sequences, given all these values
Теперь, если мы имели возможность вычислить F, мы могли бы просто просуммировать все возможные значения п(от 1 до K) и I, чтобы получить ответ на вашу проблему.
Предположим, что I = «увеличение». Мы хотим выразить F K, L (N, M, «увеличение», п а) в терминах «меньше» значения F, поэтому мы можем рекурсивно вычислять значения F, чтобы получить окончательное значение , Мы сделаем это, суммируя значение F по всем возможным значениям a n-1; то есть, по сути, мы говорим, что F равно к числу действительных последовательностей длины N-1 что может конец в п, то представьте себе, добавляя п к каждому из них.
Потому что мы знаем п является частью возрастающей последовательности (I = "увеличение"), мы знаем, что п-1 < п (мы будем скоро получите к другому делу). Мы также знаем, что п-1 должна быть в пределах L от п-1; Таким образом, макс (1, а п - Л) < = а п-1 < п.
Теперь мы имеем два случая, чтобы рассмотреть, в зависимости от того предыдущего срока п-1 было увеличение или уменьшение:
- п-1 был увеличение. Тогда мы все еще растет, так что значение
F мы заинтересованы в том,
Р К, L (N-1, М, «повышение», А н-1).
- п-1 был уменьшение. a n В настоящее время увеличивается, так что теперь будет еще один «запуск» значений. Таким образом, значение
F мы заинтересованы в том,
Р К, L (N-1, М-1, "уменьшение", А н-1).
Мы просуммировать все эти случаи для всех возможных значений п-1, чтобы получить значение F K, L (N, M, "растущий", А п). Мы можем найти F K, L (N, M, "уменьшение", а п) аналогичным образом, только мы ограничить п-1 к п < n-1 < = min (K, a n + L), и мы вычитаем 1 из M в случае № 1, а не в случае № 2.
И наконец, мы указываем базовые чехлы.F K, L (N, M, I, a n): 0, если M < 1 или M> N; 1, если N = 1.
Затем, как было отмечено выше, только суммирование по всем значениям I и п в F K, L (N, M, я, п), чтобы получить ответ к вашей оригинальной проблеме. Сложность выполнения - O(KMN)
И как вы пытались его решить? – Josh
И особенно, где вопрос? –
В третьем абзаце есть реальный вопрос. Я просто отредактировал, чтобы соответствующим образом отделить абзацы. – ElKamina