Minimize cost to reach end of an array by two forward jumps or one backward jump in each move

0 2 8 minutes read

Given an array arr[] consisting of N positive integers, the task is to find the minimum cost required to either cross the array or reach the end of the array by only moving to indices (i + 2) and (i – 1) from the i^th index.

Examples:

Input: arr[] = {5, 1, 2, 10, 100}
Output: 18
Explanation:
Optimal cost path (0 based indexing): 0 ? 2 ? 1 ? 3 ? 5
Therefore, the minimum cost = 5 + 2 + 1 + 10 = 18.

Input: arr[] = {9, 4, 6, 8, 5}
Output: 20
Explanation:
Optimal cost path (0 based indexing): 0 ? 2 ? 4
Therefore, the minimum cost = 9 + 6 + 5 = 20

Naive Approach: The given problem can be solved based on the following observations:

Since all costs are positive, it will never be an optimal option to move more than one step backward, hence to reach a particular index i of the array, either jump directly from the (i – 2)^th index or jump from (i – 1)^th to (i + 1)^th index, i.e. (2 jumps forward), followed by 1 backward jump, i.e. from (i + 1)^th index to i^th index.
Now, traverse from the end of the array recursively and for the elements at indices (i – 2) and (i – 1), calculate the minimum cost of the two. Therefore, the minimum cost to cross the array can be calculated using the following recurrence relation:

minCost(index) = minimum(minCost(index – 2) + arr[i], minCost(index – 1) + arr[i] + arr[i + 1])

Time Complexity: O(2^N)
Auxiliary Space: O(1)

Efficient Approach: The approach discussed above has both Optimal Substructure and Overlapping Subproblems. Therefore it can be optimized by either using Memoization or Tabulation. Follow the steps below to solve the problem:

Initialize an array dp[], where dp[i] stores the minimum cost to reach the i^th index.
Initialize dp[0] = arr[0] as the cost to reach the 0^th index, which is equal to the value at the 0^th index itself. Update dp[1] = arr[0] + arr[1] + arr[2], as to reach the 1^st index, jump from the 0^th index to 2^nd index indexn to the 1^st index.
Iterate over the range [2, N – 2] using a variable i and update dp[i] as the minimum of (dp[i – 2] + arr[i]) and (dp[i – 1] + arr[i] + arr[i + 1]).
For the last index (N – 1), update dp[N – 1] as minimum of (dp[N – 3] + arr[N – 1]) and (dp[N – 2]).
After completing the above steps, print the value of dp[N – 1] as the result.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum cost
// to reach the end of an array
void minCost(int arr[], int n)
{
    // Base Case: When N < 3
    if (n < 3) {
        cout << arr[0];
        return;
    }
 
    // Store the results in table
    int* dp = new int[n];
 
    // Initialize base cases
    dp[0] = arr[0];
    dp[1] = dp[0] + arr[1] + arr[2];
 
    // Iterate over the range[2, N - 2]
    // to construct the dp array
    for (int i = 2; i < n - 1; i++)
        dp[i] = min(dp[i - 2] + arr[i],
                    dp[i - 1] + arr[i]
                        + arr[i + 1]);
 
    // Handle case for the last index, i.e. N - 1
    dp[n - 1] = min(dp[n - 2],
                    dp[n - 3] + arr[n - 1]);
 
    // Print the answer
    cout << dp[n - 1];
}
 
// Driver Code
int main()
{
    int arr[] = { 9, 4, 6, 8, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
    minCost(arr, N);
 
    return 0;
}

Java

// Java Program to implement
// the above approach
import java.io.*;
import java.util.*;
 
class GFG
{
 
    // Function to find the minimum cost
    // to reach the end of an array
    static void minCost(int arr[], int n)
    {
       
        // Base Case: When N < 3
        if (n < 3) {
            System.out.println(arr[0]);
            return;
        }
 
        // Store the results in table
        int dp[] = new int[n];
 
        // Initialize base cases
        dp[0] = arr[0];
        dp[1] = dp[0] + arr[1] + arr[2];
 
        // Iterate over the range[2, N - 2]
        // to construct the dp array
        for (int i = 2; i < n - 1; i++)
            dp[i] = Math.min(dp[i - 2] + arr[i],
                           dp[i - 1] + arr[i] + arr[i + 1]);
 
        // Handle case for the last index, i.e. N - 1
        dp[n - 1] = Math.min(dp[n - 2], dp[n - 3] + arr[n - 1]);
 
        // Print the answer
        System.out.println(dp[n - 1]);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = { 9, 4, 6, 8, 5 };
        int N = arr.length;
        minCost(arr, N);
    }
}
 
// This code is contributed by Kingash.

Python3

# Python 3 program for the above approach
 
# Function to find the minimum cost
# to reach the end of an array
def minCost(arr, n):
 
    # Base Case: When N < 3
    if (n < 3):
        print(arr[0])
        return
 
    # Store the results in table
    dp = [0] * n
 
    # Initialize base cases
    dp[0] = arr[0]
    dp[1] = dp[0] + arr[1] + arr[2]
 
    # Iterate over the range[2, N - 2]
    # to construct the dp array
    for i in range(2, n - 1):
        dp[i] = min(dp[i - 2] + arr[i],
                    dp[i - 1] + arr[i]
                    + arr[i + 1])
 
    # Handle case for the last index, i.e. N - 1
    dp[n - 1] = min(dp[n - 2],
                    dp[n - 3] + arr[n - 1])
 
    # Print the answer
    print(dp[n - 1])
 
# Driver Code
if __name__ == "__main__":
 
    arr = [9, 4, 6, 8, 5]
    N = len(arr)
    minCost(arr, N)
 
    # This code is contributed by ukasp.

C#

// C# Program to implement
// the above approach
using System;
public class GFG
{
 
  // Function to find the minimum cost
  // to reach the end of an array
  static void minCost(int []arr, int n)
  {
 
    // Base Case: When N < 3
    if (n < 3) {
      Console.WriteLine(arr[0]);
      return;
    }
 
    // Store the results in table
    int []dp = new int[n];
 
    // Initialize base cases
    dp[0] = arr[0];
    dp[1] = dp[0] + arr[1] + arr[2];
 
    // Iterate over the range[2, N - 2]
    // to construct the dp array
    for (int i = 2; i < n - 1; i++)
      dp[i] = Math.Min(dp[i - 2] + arr[i],
                       dp[i - 1] + arr[i] + arr[i + 1]);
 
    // Handle case for the last index, i.e. N - 1
    dp[n - 1] = Math.Min(dp[n - 2], dp[n - 3] + arr[n - 1]);
 
    // Print the answer
    Console.WriteLine(dp[n - 1]);
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
    int []arr = { 9, 4, 6, 8, 5 };
    int N = arr.Length;
    minCost(arr, N);
  }
}
 
// This code is contributed by AnkThon

Javascript

<script>
 
// Javascript program for the above approach
 
    // Function to find the minimum cost
    // to reach the end of an array
    function minCost(arr, n)
    {
        
        // Base Case: When N < 3
        if (n < 3) {
            document.write(arr[0]);
            return;
        }
  
        // Store the results in table
        let dp = [];
  
        // Initialize base cases
        dp[0] = arr[0];
        dp[1] = dp[0] + arr[1] + arr[2];
  
        // Iterate over the range[2, N - 2]
        // to construct the dp array
        for (let i = 2; i < n - 1; i++)
            dp[i] = Math.min(dp[i - 2] + arr[i],
                           dp[i - 1] + arr[i] + arr[i + 1]);
  
        // Handle case for the last index, i.e. N - 1
        dp[n - 1] = Math.min(dp[n - 2], dp[n - 3] + arr[n - 1]);
  
        // Print the answer
        document.write(dp[n - 1]);
    }
 
// Driver Code
 
        let arr = [ 9, 4, 6, 8, 5 ];
        let N = arr.length;
        minCost(arr, N);
 
</script>

Output

Time Complexity: O(N)
Auxiliary Space: O(N)

Algorithm:

Initialize two variables prevPrev and prev as arr[0] and arr[0]+arr[1]+arr[2] respectively.
Iterate over the range [2, N-1] and for each index i:
a. Calculate the minimum cost to reach this index by comparing dp[i-1]+arr[i]+arr[i+1] and dp[i-2]+arr[i].
b. Update prevPrev as prev and prev as dp[i] for the next iteration.
The minimum cost to reach the end of the array is the minimum of prevPrev and prev.

C++

#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum cost
// to reach the end of an array
void minCost(int arr[], int n)
{
    // Base Case: When N < 3
    if (n < 3) {
        cout << arr[0];
        return;
    }
 
    // Initialize variables prevPrev and prev
    int prevPrev = arr[0];
    int prev = arr[0] + arr[1] + arr[2];
 
    // Iterate over the range[2, N - 1]
    // to construct the dp array
    for (int i = 2; i < n - 1; i++) {
        int curr = min(prevPrev + arr[i], prev + arr[i] + arr[i + 1]);
        prevPrev = prev;
        prev = curr;
    }
 
    // Print the answer
    cout << min(prevPrev, prev);
}
 
// Driver Code
int main()
{
    int arr[] = { 9, 4, 6, 8, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
    minCost(arr, N);
 
    return 0;
}

Java

import java.lang.*;
 
class Main {
    public static void minCost(int[] arr, int n)
    {
        // Base Case: When N < 3
        if (n < 3) {
            System.out.println(arr[0]);
            return;
        }
 
        // Initialize variables prevPrev and prev
        int prevPrev = arr[0];
        int prev = arr[0] + arr[1] + arr[2];
 
        // Iterate over the range[2, N - 1]
        // to construct the dp array
        for (int i = 2; i < n - 1; i++) {
            int curr = Math.min(prevPrev + arr[i],
                                prev + arr[i] + arr[i + 1]);
            prevPrev = prev;
            prev = curr;
        }
 
        // Print the answer
        System.out.println(Math.min(prevPrev, prev));
    }
 
    public static void main(String[] args)
    {
        int[] arr = { 9, 4, 6, 8, 5 };
        int N = arr.length;
        minCost(arr, N);
    }
}

Python3

def minCost(arr, n):
    # Base Case: When N < 3
    if n < 3:
        return arr[0]
 
    # Initialize variables prevPrev and prev
    prevPrev = arr[0]
    prev = arr[0] + arr[1] + arr[2]
 
    # Iterate over the range[2, N - 1]
    # to construct the dp array
    for i in range(2, n - 1):
        curr = min(prevPrev + arr[i], prev + arr[i] + arr[i + 1])
        prevPrev = prev
        prev = curr
 
    # Print the answer
    return min(prevPrev, prev)
 
 
arr = [9, 4, 6, 8, 5]
N = len(arr)
print(minCost(arr, N))

Javascript

// Function to find the minimum cost
// to reach the end of an array
function minCost(arr, n) {
    // Base Case: When N < 3
    if (n < 3) {
        console.log(arr[0]);
        return;
    }
 
    // Initialize variables prevPrev and prev
    let prevPrev = arr[0];
    let prev = arr[0] + arr[1] + arr[2];
 
    // Iterate over the range[2, N - 1]
    // to construct the dp array
    for (let i = 2; i < n - 1; i++) {
        let curr = Math.min(prevPrev + arr[i], prev + arr[i] + arr[i + 1]);
        prevPrev = prev;
        prev = curr;
    }
 
    // Print the answer
    console.log(Math.min(prevPrev, prev));
}
 
// Driver Code
const arr = [9, 4, 6, 8, 5];
const N = arr.length;
minCost(arr, N);

Output

Complexity Analysis:

Time Complexity: O(N), where N is the size of the array. We are iterating over the array once to calculate the minimum cost to reach each index.

Space Complexity: O(1). We are not using any extra space for storing the intermediate results. We are just using two variables prevPrev and prev to store the results for the previous iterations.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!