educative.io

Educative

For example {2,3,4,5}, should the answer be 2

In the following example, we are able to go from step 0 to step 3. I am assuming, this is because we can take 3 steps.

Fee: {1,2,5,2,1,2}
Output: 3
Explanation: Starting from index '0', we can reach the top through: 0->3->top

So, for the following example, why can’t it be just 0 -> top(index 3). Then cost will be just 2. why do we need to stop at index 1

Number of stairs (n): 4
Fee: {2,3,4,5}
Output: 5 Explanation: Starting from index '0', we can reach the top through: 0->1->top
2 Likes

Hi Chandra!

In the first example, the minimum fee was 3 since it took three steps each time, once to go from step 0 to step 3, and then from step 3 to the top. The fee is calculated as fee[0] + fee[3] = 1 + 2 = 3.

In the second example, if we initially take three steps, we will reach step 3 which has a cost of 5. In order to reach the top, we must take one more step, giving us an additional cost of 5. The fee, in this case, will be calculated as fee[0] + fee[3] = 2 + 5 = 7.

Therefore, a better alternative is to initially take one step to land on step 1 (cost = 3), and then take three steps to reach the top, giving us a total fee of 5 (fee[0] + fee[1] = 2 + 3 = 5)

The tricky part is going past the last step of the staircase.

“reach the top of the staircase (beyond the top-most step).”

So in Example 1, 0->3->top works because a step of size 3 from index 3 goes to index 6, which is past the last step at index 5.

And in Example 2, index 0->4 is not sufficient to go past 4, so it goes 0->1->top (top being a step beyond index 4, so the fee at index 4 must be counted).