Максимальное количество прыжков для достижения конца массива при условии, что индекс i может совершать прыжки arr[i]

Учитывая целое число N и массив arr[ ] размера N, задача состоит в том, чтобы найти максимальное количество прыжков для достижения конца массива с учетом ограничения, согласно которому из индекса i можно совершать прыжки arr[i] и достигать позиции i+arr [я] .

Примеры:

Input: N = 5, arr[] = {2, 3, 5, 7, 9}
Output: 12 
Explanation:
At index 0 make 2 jumps and move to index 2 and make 5 jumps after that to reach index 7 which is out of the array so total number of jumps is (2+5)=7. 
At index 1 make 3+9= 12 jumps 
At index 2 make 5 jumps
At index 3 make 7 jumps
At index 4 make 9 jumps 

Input: arr[]={2, 2, 1, 2, 3, 3}
Output: 8

Подход: Идея состоит в том, чтобы использовать динамическое программирование для решения этой проблемы. Выполните следующие действия, чтобы решить проблему.

• Инициализируйте массив dp размера N с помощью 0. dp[i] хранит количество прыжков, необходимых для достижения конца массива с индекса i . Кроме того, инициализируйте целое число и значение 0.
• Пройдите через массив с конца массива, используя цикл for
  • Присвойте arr[i] значению dp[i] , так как arr[i] — это наименьшее количество переходов из этого индекса.
  • Теперь инициализируйте переменную, скажем j , и назначьте j = i+arr[i].
  • Если значение j меньше, чем N , добавьте dp[j] к dp[i] .
  • Обновите значение ans как max( ans , dp[i] )
• После выполнения вышеуказанных шагов выведите значение ans.

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