2
$\begingroup$

(Source: https://leetcode.com/problems/jump-game-ii/)

Consider the following problem: Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example, if nums = [2,3,1,1,4] then the minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Greedy Algorithm: Let $n(x)$ be the number located at index $x$. At each jump, jump to the index $j$ that maximizes $j + n(j)$. In the above example, starting at index $0$, we can jump $1$ or $2$ jumps. If we jump once to index $1$, then the objective value is $1 + n(1) = 4$. If we jump twice to index $2$, then the objective value is $2 + n(2) = 3$. Thus, we must jump once to index $1$, and so on.

Prove that the greedy algorithm is correct.

I am trying to prove this with greedy stays ahead. The working inductive hypothesis is that at jump $k$, $o_k + n(o_k) \leq g_k + n(g_k)$ where $o_k$ is the index of optimal solution at jump $k$ and $g_k$ is the index of greedy solution.

Then, at jump $k+1$, we know that $o_{k+1} \leq o_k + n(o_k)$ - this is the farthest index we can jump to - and similarly for $g_{k+1}$.

I am struggling to finish the proof though, and cannot seem to manipulate the inequalities to conclude that $o_{k+1} + n(o_{k+1}) \leq g_{k+1} + n(g_{k+1})$ - could someone help on this matter?

$\endgroup$

1 Answer 1

2
$\begingroup$

The essential problem with your approach is that you are trying to prove a proposition that is too weak to to sustain the induction step.

Here is the proposition that we should prove:

For $k$ ranging from $1$ to the number of jumps in the greedy solution,

  • $a_k + n(a_k) \leq g_k + n(g_k)$, where $a_k$ is the index of an arbitrary jump sequences at jump $k$ and $g_k$ is the index of greedy solution at jumtp $k$, and
  • for all $0\leq m\le g_k$, $m+n(m)\leq g_k + n(g_k)$.

I believe that you will be able to prove the proposition above using induction on $k$.

$\endgroup$
3
  • $\begingroup$ Hm I am still having some issues even with the strong induction - I'm not sure where to use it. At jump $k+1$, we know that $a_{k+1} \leq g_k + n(g_k)$ by IH, but I don't see where I would ever use the strong induction hypothesis as we certainly cannot assume that $a_{k+1} \leq g_k$ $\endgroup$
    – a6623
    Dec 12, 2021 at 21:49
  • $\begingroup$ As induction hypothesis, suppose the proposition is true for $k$. Let $a_{k+1}=a_k+t$ for some $t$, $0\le t \le n(a_k)$. There are two cases. Case one, $a_{k+1}\le g_k$, in which case we can use the induction hypothesis. Case two, $a_{a+1}=g_k+u$ for $u\gt0$, where we must have $u\le n(g_k)$, also thanks to the induction hypothesis. In case two, we can use how our algorithm is greedy. $\endgroup$
    – John L.
    Dec 13, 2021 at 3:19
  • $\begingroup$ Here is another approach that is slightly different. For $k$ ranging from $1$ to the number of jumps in the greedy solution, let $x_k$ be the maximum index of an arbitrary jump sequence at jump $k$ and $g_k$ be the index of greedy solution at jump $k$. We can prove that $m+n(m)\leq g_k + n(g_k)$ for all $m$ and $k$, $0\le m\le x_k$. $\endgroup$
    – John L.
    Dec 13, 2021 at 3:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.