EDIT: My review: Regarding your question - firstly, you cannot jump from towers(1) to towers(4). towers(1) = 2, so you can only reach 1+2 = towers(3).
So that's a basic misunderstanding of the problem.
But - your code actually works, and its very efficient. Basically O(n). Also, with vnp's changes, it's even more efficient (albeit not recursive) (but still O(n)).
I think Dynamic Programming won't help you so much as you already came to a very efficient solution. Here's how it did help me to improve my first recursive solution which was really not efficient O(2^n) to a O(n^2):
Here's my solutions (in C#, can be "easily" adapted to C):
I started with a recursive solution, that breaks the big problem to smaller ones (basically defers the decision on complicated matters until the simpler matters are solved) - there is basically 2 base cases - either the tower is bigger than remaining size (return true) or it's 0 (return false). For the rest you have to recurse. The loop starts from the farthest you can go from the first tower (recurse for that tower etc.), and then goes down... up to making just 1 step:
public static bool IsHoppableNaive(int array, int len)
if (array >= len)
if (array <= 0)
bool ret = false;
for (int i = array; i >= 1; i--)
var newArray = new int[len - i];
Array.Copy(array, i, newArray, 0, len - i);
ret = ret || IsHoppableNaive(newArray, len - i);
if (ret) // optimization - no point in continuing if already true...
Time complexity of this is 2^(n-1)... So this could be very inefficient. That is why it can be improved with Dynamic Programming.
For DP solution, I first solved this theoretically by constructing a table of n x n. The way you fill this table is for each row you take the tower number and set the subsequent columns to true, (representing can I reach the next tower? and not can I reach the current tower, as you are already in it). Otherwise you give it false (for the first row), and for any subsequent row you take whatever is in the upper row.
the * are ones that are true thanks to their above row, and not for the actual number.
(EDIT: How did I came up with this? If we go over a bad case solution - say 5, 4, 3, 2, 1, 0 - we can see that we end up computing a lot of stuff we already computed before - this is where DP can help us, if we store these calculations somewhere; So - the entire point of "the above row" is to tell us which calculations we don't need to redo).
Here's the code:
public static bool IsHoppableDP(int array, int len)
bool[,] dp = new bool[len, len];
for (int i = 0; i < len; i++)
for (int j = i; j < len; j++)
if (j < i + array[i])
dp[i, j] = true;
else if (i > 0)
dp[i, j] = dp[i - 1, j];
dp[i, j] = false;
return dp[len - 1, len - 1];
So, here we can save from bad cases, but even good cases will take n + (n-1) + (n-2) + ... + 1 - which is n*(n+1)/2 ... basically also O(n^2). Which is a major improvement over the O(2^n)
Finally there is the "Simple" solution shown here, without the helper method/function.
The "simple" solution (it was actually far less simple to write that tricky getNext function) seems to offer the best time and space complexity. It basically uses some "heuristics", i.e. we know that the best tower to jump to is the one that offers the farthest range. The farthest range can be computed by adding the current index with the current value. We just have to be careful not to get out-of-bounds Argument-Exception...
Here's the code:
public static bool IsHoppableSimple(int array, int len)
int current = 0;
if (current >= len)
if (array[current] == 0)
current = bestNextStep(current, array, len);
private static int bestNextStep(int current, int array, int len)
int best = current + array[current]; // Assuming the current farthest is the best
for (int i = current; i < current + array[current]; i++) // find the actual best
if (i + array[i] > len)
return i + array[i]; // caution against getting outside of the bounds of the array
if (i + array[i] > best)
best = i + array[i];
Time complexity here is O(n) [we only traverse the array once], and space complexity is O(1) [we do everything in place].