### Introduction

This problem is based on one of the popular topics of __Data Structure____s__. I.e., Dynamic Programming, and Greedy Algorithms. Dynamic programming is an optimization for recursion. In recursion, we calculate the same calculation again and again, but in DP, this problem can be overcome.

Greedy algorithms use a technique to build the solution piece by piece and choose the piece which offers the most immediate benefit.

The Jump Game II is a problem where we will find minimum steps to reach the final index from the starting index.

We will see different approaches for solving this problem.

Let's move on to our problem statement.

### Problem Statement

We are given an array, standing on the first index and taking a minimum number of steps to reach the last index. Every integer in the array represents the maximum number of steps a person can take.

Our goal is to get the minimum jumps from source to destination.

You can understand it like this: suppose your first index is your house, and the destination you have to reach is your last index. Now you have to tell how many minimum steps. At each step, you will be given how many steps you can take.

Note:

- The array of non-negative integers.
- You will always reach the last index.

For example:

**Input:**

**Output:**

** 2**

Let me give you a brief about this example through a pictorial representation.

This problem is easy if we have to do it in O(n2) time, but it becomes challenging to solve it in O(n) time complexity.

Try to solve it out for another example:

**Input:**

5,9,3,2,1,0,2,3,3,1,0

What will be the minimum jumps to reach the last index??

- From index 0 we can at max go 0 + 5 = 5
- From index 1, we can at max go 1 + 9 = 10
- From index 2, we can at max go 2 + 3 = 5,
- From index 3,we can at max go 3 + 2 = 5
- From index 4 we can at max go, 4 + 1 = 5
- From index 5, we can at max go 5 + 0 = 5
- From index 6, we can at max go 6 + 2 = 8
- From index 7, we can at max go 7 + 3 = 10
- From index 8, we can at max go 8 + 3 = 11 (this is the last index)
- First, we will check how to reach 8.

** **

**Minimum index to reach 8**

index 0,we can at max go 0 + 5 = 5

index 1, we can at max go 1 + 9 = 10

We have to first reach the index 1

**Minimum index to reach at index 1**

index 0,we can at max go 0 + 5 = 5, yes. So, 3 total jumps.

If the problem statement is clear, let's move to our approach.

__Note: Please try to solve Jump Game II on Coding Ninjas Studio before stepping into the solution__