Проверьте, можно ли достичь конца данной двоичной строки, выбрав значение перехода между заданным диапазоном

Для заданных двух положительных целых чисел L и R и двоичной строки S размера N задача состоит в том, чтобы проверить, достигается ли конец строки с индекса 0 серией скачков индексов, скажем, i таких, что S[i] равно В диапазоне [L, R] разрешено 0 прыжков. Если дозвониться можно, то выведите Yes . В противном случае выведите Нет .

Примеры:

Input: S = “011010”, L = 2, R = 3
Output: Yes
Explanation:
Following are the series of moves having characters at that indices as 0:
S[0](= 0) -> S[3](= 0) -> S[5](= 0) and S[5] is the end of the string S.
Therefore, print Yes.

Input: S = “01101110”, L = 2, R = 3
Output: No

Подход: Вышеупомянутая проблема может быть решена с помощью динамического программирования, идея состоит в том, чтобы поддерживать одномерный массив, скажем, dp[] , где dp[i] будет хранить возможность достижения i ^-й позиции и соответствующим образом обновлять каждый индекс. Ниже приведены шаги:

• Инициализируйте массив dp[] таким образом, чтобы dp[i] хранил информацию о том, можно ли достичь любого индекса i из индекса 0 или нет. Обновите значение dp[0] на 1 , так как это текущий постоянный индекс.
• Инициализируйте переменную, pre как 0 , которая хранит количество индексов, из которых доступен текущий индекс.
• Переберите диапазон [1, N) и обновите значение переменной pre следующим образом:
  • Если значение ( i >= minJump ), то увеличьте значение pre на dp[i – minJump] .
  • Если значение ( i > maxJump ), то уменьшите значение pre на dp[i – maxJump – 1] .
• Если значение pre положительно, то существует по крайней мере 1 индекс, из которого доступен текущий индекс. Поэтому обновите значение dp[i] = 1 , если значение S[i] = 0 .
• После выполнения вышеуказанных шагов, если значение dp[N – 1] положительное, выведите Yes . В противном случае выведите Нет .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(N)