Minimum Cost to Reach Every Position

Difficulty: Easy | Acceptance: 83.30% | Paid: No Topics: Array

You are given a 0-indexed integer array cost of length n, where cost[i] represents the cost to land on index i. You start at index 0.

From index i, you can jump to index i + 1 or i + 2.

Return an array ans of length n, where ans[i] is the minimum cost to reach index i.

• Examples
• Constraints
• Dynamic Programming (Iterative)
• Dynamic Programming (In-Place)
• Recursion with Memoization

Examples

Example 1:

Input: cost = [5, 3, 4, 2]
Output: [5, 8, 9, 10]
Explanation:
- ans[0] = cost[0] = 5
- ans[1] = cost[0] + cost[1] = 5 + 3 = 8
- ans[2] = min(ans[0], ans[1]) + cost[2] = min(5, 8) + 4 = 9
- ans[3] = min(ans[1], ans[2]) + cost[3] = min(8, 9) + 2 = 10

Example 2:

Input: cost = [10, 20]
Output: [10, 30]
Explanation:
- ans[0] = cost[0] = 10
- ans[1] = cost[0] + cost[1] = 10 + 20 = 30

Constraints

- 1 <= n == cost.length <= 100
- 1 <= cost[i] <= 100

Dynamic Programming (Iterative)

Intuition We can solve this problem by building up the solution from the base cases. Since we can only reach index i from i-1 or i-2, the minimum cost to reach i is the cost to land on i plus the minimum cost to reach either of the two previous positions.

Steps

• Initialize an array ans of the same length as cost.
• Set ans[0] = cost[0] and ans[1] = cost[0] + cost[1].
• Iterate from index 2 to n-1. For each index i, calculate ans[i] = cost[i] + min(ans[i-1], ans[i-2]).
• Return the ans array.

class Solution:
    def minCost(self, cost: list[int]) -> list[int]:
        n = len(cost)
        ans = [0] * n
        ans[0] = cost[0]
        ans[1] = cost[0] + cost[1]
        
        for i in range(2, n):
            ans[i] = cost[i] + min(ans[i-1], ans[i-2])
            
        return ans

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Uses O(n) space to store the result array.

Dynamic Programming (In-Place)

Intuition We can optimize the auxiliary space used by modifying the input cost array directly to store the cumulative minimum costs. This avoids allocating a new array for the result.

Steps

• Update cost[1] by adding cost[0] to it.
• Iterate from index 2 to n-1. Update cost[i] by adding the minimum of cost[i-1] and cost[i-2].
• Return the modified cost array.

class Solution:
    def minCost(self, cost: list[int]) -> list[int]:
        n = len(cost)
        cost[1] += cost[0]
        
        for i in range(2, n):
            cost[i] += min(cost[i-1], cost[i-2])
            
        return cost

Complexity

• Time: O(n)
• Space: O(1) auxiliary (excluding input/output storage)
• Notes: Modifies the input array in place.

Recursion with Memoization

Intuition We can define the problem recursively: the minimum cost to reach index i is cost[i] plus the minimum cost to reach i-1 or i-2. To avoid redundant calculations, we memoize the results of subproblems.

Steps

• Create a memoization array (or map) initialized to -1 or null.
• Define a recursive function solve(i) that returns the minimum cost to reach index i.
• Base cases: if i == 0 return cost[0]; if i == 1 return cost[0] + cost[1].
• If memo[i] is already calculated, return it.
• Otherwise, calculate memo[i] = cost[i] + min(solve(i-1), solve(i-2)).
• Iterate through all indices 0 to n-1 to populate the result array using the recursive function.

class Solution:
    def minCost(self, cost: list[int]) -> list[int]:
        n = len(cost)
        memo = {}
        
        def solve(i):
            if i == 0:
                return cost[0]
            if i == 1:
                return cost[0] + cost[1]
            if i in memo:
                return memo[i]
            memo[i] = cost[i] + min(solve(i-1), solve(i-2))
            return memo[i]
        
        return [solve(i) for i in range(n)]

Complexity

• Time: O(n)
• Space: O(n) for recursion stack and memoization
• Notes: May cause stack overflow for large n due to recursion depth.