GATE CS 2014 Set 3 Q37 — Algorithm Design: Dynamic Programming

To find the minimum number of steps $T(k)$ to reach $100$ from any position $k$, we analyze the choices available at position $k$.

At any position $k$, we can always make a standard move of $1$ unit to the right, reaching $k+1$. Additionally, if there is a shortcut starting at $k$ to some destination $j$, we can also choose to jump directly to $j$.

For $k = 9$:

1. Standard move: Move $1$ unit right to reach $10$. The remaining steps needed would be $T(10)$.
2. Shortcut move: We are given that there is a shortcut from $9$ to $15$. Taking this shortcut leads to position $15$. The remaining steps needed would be $T(15)$.

Since we want to minimize the number of steps, the optimal choice from $9$ is given by the recurrence:

Comparing this with the given equation:

We identify that the set of values for $\{y, z\}$ is $\{10, 15\}$.

Thus, the product $yz$ is: