Minimum Cost to Reach the End

Description:

You are given an array cost where cost[i] is the cost of stepping on the i-th stone (0-indexed). You start at index 0, and your goal is to reach index n (the end of the array).

At each move, you can jump forward up to k steps.

Return the minimum total cost to reach the end of the array.

Constraints:

1 <= n <= 10^3

1 <= cost[i] <= 10^4

1 <= k <= n

How to approach?

Brute force

function minCost(cost: number[], k: number): number {
    const n = cost.length;
    const dp = new Array(n + 1).fill(Infinity);
    dp[0] = 0;

    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= k; j++) {
            if (i - j >= 0) {
                dp[i] = Math.min(dp[i], dp[i - j] + cost[i - 1]);
            }
        }
    }
    return dp[n];
}

1. create n variable as cost array length.
2. create dp array which has length of n+1 and fill it with Infinity.
3. and set 0 index element as 0, since there is no cost before it starts.
4. create for loop starting with 1 and including n value and create inner for loop to use the j index which is smaller than k steps.
5. when i-j is bigger/same than 0, set dp[i] as the minimum value between current dp[i] and sum of current cost and previous dp value using k steps.
6. it means it check all the up to k steps to compare which one is the smallest value to add.
7. and lastly return dp[n] since it's accumulation of the minimum cost using up to k steps.

summary

checking all previous k steps to get the smallest value accumulation.

O(n*k) time complexity and dp takes O(n) space complexity.

Dynamic Programming & window sliding

function minCost(cost: number[], k: number): number {
    const n = cost.length;
    const dp = new Array(n + 1).fill(Infinity);
    dp[0] = 0;

    const deque: number[] = [0];

    for (let i = 1; i <= n; i++) {
        while (deque.length > 0 && deque[0] < i - k) {
            deque.shift();
        }

        dp[i] = dp[deque[0]] + cost[i - 1];

        while (deque.length > 0 && dp[deque[deque.length - 1]] >= dp[i]) {
            deque.pop();
        }

        deque.push(i);
    }

    return dp[n];
}

1. create n which is length of cost array.
2. dp is array has n+1 length and fill it with Infinity.
3. dp's 0 index element will be 0.
4. create deque which is number array. and set first index value as 0. this will store the indices of dp array.
5. create for loop starting with 1 and including n.
6. set while condition to check the deque's 0 index value is smaller than i-k, and if it is then remove the 0 index value in deque. because it is out of the window which dp can use.
7. and set dp[i] using deque[0] index and plus current cost value at i-1 since cost using 0 based index.
8. and also check the deque's last element using current dp[i], if it is bigger/same than the current dp[i], pop it out since deque needs to be maintained as monotonic.
9. and there is nothing to remove, then push the i index into deque.
10. lastly return the dp[n] since it's accumulated so far as the best solutions to get the minimum cost.

summary

This will have O(n) time complexity since it doesn't have to check up-to-k steps so far. use deque to check the best indices of dp to get the minimum cost on cost array using k value to jump.