Categories

# Hopper Tower Problem using Dynamic Programming

Write a function to determine whether a person can reach the other end of the array if he starts at index 0 and if he cannot hop more than the value contained at that index.

```var jumper = [];
var arr = [4, 0, 0, 1];

function hopper(index) {
if (index + arr[index] >= arr.length) {
jumper[index] = true;
return;
} else {
for (var i = index + 1; i <= index + arr[index]; i++) {
if (jumper[i]) {
jumper[index] = true;
return;
}
}
jumper[index] = false;
}
}

function isReachable() {
for (var j = arr.length - 1; j >= 0; j--) {
hopper(j);
}
return jumper[0];
}

isReachable()
```

Output

```isReachable => true
jumper => [true, false, false, true]
```

Time Complexity: O(n^2)
Space Complexity: O(n)
Demo

## Get Minimum Hops

To get the minimum hops, now we need to keep track of the hops at each index using another array or we can create a Data Structure (here Object) to keep track of them.

```var jumper = [];
var mjumper = [];
var arr = [4, 1, 1, 1];

function hopper(index) {
if (index + arr[index] >= arr.length) {
jumper[index] = true;
mjumper[index] = 1;
} else {
for (var i = index + 1; i <= index + arr[index]; i++) {
if (jumper[i]) {
if (jumper[index]) {
mjumper[index] = Math.min(mjumper[i] + 1, mjumper[index]);
} else {
jumper[index] = true;
mjumper[index] = mjumper[i] + 1;
}
}
}
if (!jumper[index]) {
jumper[index] = false;
}
}
}

function getMinimumSteps() {
for (var j = arr.length - 1; j >= 0; j--) {
hopper(j);
}

if (jumper[0])
return mjumper[0];
else return -1;
}

getMinimumSteps();
```

Output

```1
```

Time Complexity: O(n^2)
Space Complexity: O(n)
Demo