Minimize cost of choosing and skipping array elements to reach end of the given array

0 0 11 minutes read

Given an integer X and an array cost[] consisting of N integers, the task is to find the minimum cost to reach the end of the given array starting from the first element based on the following constraints:

Cost to visit point i is cost[i] where 1 ? i ? N.
Cost to skip point i is min(cost[i], X) where 1 ? i ? N.
At most 2 points can be skipped in a row.
First and last positions cannot be skipped.

Examples:

Input: N = 6, X = 4, cost[] = {6, 3, 9, 2, 1, 3}
Output: 19
Explanation:
Follow the steps below:
Step 1: Choose element at 1. Sum = 6
Step 2: Choose element at 2. Sum = 6 + 3 = 9
Step 3: Skip element at 3. Sum = 6 + 3 + 4 = 13
Step 4: Choose element at 4. Sum = 6 + 3 + 4 + 2 = 15
Step 5: Choose element at 5. Sum = 6 + 3 + 4 + 2 + 1 = 16
Step 6: Choose element at 6. Sum = 6 + 3 + 4 + 2 + 1 + 3 = 19
Hence, the minimum cost is 19.

Input: N = 7, X = 4, cost[] = {6, 3, 9, 2, 1, 3, 4}
Output: 23
Explanation:
Follow the steps below:
Step 1: Choose element at 1. Sum = 6
Step 2: Choose element at 2. Sum = 6+3 = 9
Step 3: Skip element at 3. Sum = 6+3+4 = 13
Step 4: Choose element at 4. Sum = 6 + 3 + 4 + 2 = 15
Step 5: Choose element at 5. Sum = 6+3+4+2+1 = 16
Step 6: Choose element at 6. Sum = 6+3+4+2+1+3 = 19
Step 7: Choose element at 6. Sum = 6 + 3 + 4 + 2 + 1 + 3 + 4 = 23
Hence, the minimum cost is 23.

Naive Approach: The simplest approach is to generate all possible solutions by considering or skipping certain positions. There are two options for each element i.e., it can be skipped or can be chosen. Therefore, there can be at most 2^N combinations. Check that in each combination, no more than 3 positions are skipped. Among those combinations, choose the one having the minimum cost and print the minimum cost.

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

Efficient Approach: To optimize the above approach, the idea is to use Dynamic Programming and observe that if any position i is skipped, the cost is increased by cost[i] or X but if the cost is increased by cost[i] then it’s best to choose that position as choosing the position also increases the cost by cost[i]. This implies that the minimum cost to reach position i can be found by taking the minimum among the minimum cost to reach position (i – 1), X + the minimum cost to reach position (i – 2) and 2X + the minimum cost to reach position (i – 3).

Therefore, the dp transition is as follows:

dp[i] = cost[i] + min(dp[i-1], min(2*X + dp[i-2], 2*X + dp[i-3]))
where,
dp[i] stores the minimum answer to reach position i from position 0.

Follow the below steps to solve the problem:

Initialize an array dp[] where dp[i] will store the minimum answer to reach position i from position 0.
Traverse the given array cost[] over the range [0, N – 1] and at each position i, update dp[i] as:

cost[i] + min(dp[i-1], min(2*X + dp[i-2], 2*X + dp[i-3]))

After the above steps, print dp[N – 1] which stores the answer to reach position (N – 1) from position 0.

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 the array from
// the first element
void minimumCost(int* cost, int n, int x)
{
    // Store the results
    vector<int> dp(n + 2, 0);
 
    // Consider first index cost
    dp[0] = cost[0];
 
    // Find answer for each position i
    for (int i = 1; i < n; i++) {
 
        // First Element
        if (i == 1)
            dp[i] = cost[i] + dp[i - 1];
 
        // Second Element
        if (i == 2)
            dp[i] = cost[i]
                    + min(dp[i - 1],
                          x + dp[i - 2]);
 
        // For remaining element
        if (i >= 3)
 
            // Consider min cost for
            // skipping
            dp[i] = cost[i]
                    + min(dp[i - 1],
                          min(x + dp[i - 2],
                              2 * x + dp[i - 3]));
    }
 
    // Last index represents the
    // minimum total cost
    cout << dp[n - 1];
}
 
// Driver Code
int main()
{
    // Given X
    int X = 4;
 
    // Given array cost[]
    int cost[] = { 6, 3, 9, 2, 1, 3 };
 
    int N = sizeof(cost) / sizeof(cost[0]);
 
    // Function Call
    minimumCost(cost, N, X);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG{
 
// Function to find the minimum cost
// to reach the end of the array from
// the first element
static void minimumCost(int[] cost, int n, int x)
{
     
    // Store the results
    int[] dp = new int[n + 2];
 
    // Consider first index cost
    dp[0] = cost[0];
 
    // Find answer for each position i
    for(int i = 1; i < n; i++)
    {
         
        // First Element
        if (i == 1)
            dp[i] = cost[i] + dp[i - 1];
 
        // Second Element
        if (i == 2)
            dp[i] = cost[i] + Math.min(dp[i - 1], 
                                   x + dp[i - 2]);
 
        // For remaining element
        if (i >= 3)
 
            // Consider min cost for
            // skipping
            dp[i] = cost[i] + Math.min(dp[i - 1],
                          Math.min(x + dp[i - 2],
                               2 * x + dp[i - 3]));
    }
 
    // Last index represents the
    // minimum total cost
    System.out.println(dp[n - 1]);
}
 
// Driver Code
public static void main(String[] args)
{
 
    // Given X
    int X = 4;
 
    // Given array cost[]
    int[] cost = { 6, 3, 9, 2, 1, 3 };
 
    int N = cost.length;
 
    // Function Call
    minimumCost(cost, N, X);
}
}
 
// This code is contributed by akhilsaini

Python3

# Python3 program for the above approach
 
# Function to find the minimum cost
# to reach the end of the array from
# the first element
def minimumCost(cost, n, x):
     
    # Store the results
    dp = [0] * (n + 2)
 
    # Consider first index cost
    dp[0] = cost[0]
 
    # Find answer for each position i
    for i in range(1, n):
         
        # First Element
        if (i == 1):
            dp[i] = cost[i] + dp[i - 1]
 
        # Second Element
        if (i == 2):
            dp[i] = cost[i] + min(dp[i - 1], 
                              x + dp[i - 2])
 
        # For remaining element
        if (i >= 3):
 
            # Consider min cost for
            # skipping
            dp[i] = (cost[i] +
                   min(dp[i - 1], 
                   min(x + dp[i - 2],
                   2 * x + dp[i - 3])))
 
    # Last index represents the
    # minimum total cost
    print(dp[n - 1])
 
# Driver Code
if __name__ == '__main__':
     
    # Given X
    X = 4
 
    # Given array cost[]
    cost = [ 6, 3, 9, 2, 1, 3 ]
 
    N = len(cost)
 
    # Function Call
    minimumCost(cost, N, X)
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find the minimum cost
// to reach the end of the array from
// the first element
static void minimumCost(int[] cost, int n, int x)
{
     
    // Store the results
    int[] dp = new int[n + 2];
 
    // Consider first index cost
    dp[0] = cost[0];
 
    // Find answer for each position i
    for(int i = 1; i < n; i++)
    {
         
        // First Element
        if (i == 1)
            dp[i] = cost[i] + dp[i - 1];
 
        // Second Element
        if (i == 2)
            dp[i] = cost[i] + Math.Min(dp[i - 1],
                                   x + dp[i - 2]);
 
        // For remaining element
        if (i >= 3)
         
            // Consider min cost for
            // skipping
            dp[i] = cost[i] + Math.Min(dp[i - 1],
                          Math.Min(x + dp[i - 2],
                               2 * x + dp[i - 3]));
    }
 
    // Last index represents the
    // minimum total cost
    Console.WriteLine(dp[n - 1]);
}
 
// Driver Code
public static void Main()
{
     
    // Given X
    int X = 4;
 
    // Given array cost[]
    int[] cost = { 6, 3, 9, 2, 1, 3 };
 
    int N = cost.Length;
 
    // Function Call
    minimumCost(cost, N, X);
}
}
 
// This code is contributed by akhilsaini

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to find the minimum cost
// to reach the end of the array from
// the first element
function minimumCost(cost, n, x)
{
     
    // Store the results
    let dp = [];
  
    // Consider first index cost
    dp[0] = cost[0];
  
    // Find answer for each position i
    for(let i = 1; i < n; i++)
    {
          
        // First Element
        if (i == 1)
            dp[i] = cost[i] + dp[i - 1];
  
        // Second Element
        if (i == 2)
            dp[i] = cost[i] + Math.min(dp[i - 1],
                                   x + dp[i - 2]);
  
        // For remaining element
        if (i >= 3)
  
            // Consider min cost for
            // skipping
            dp[i] = cost[i] + Math.min(dp[i - 1],
                          Math.min(x + dp[i - 2],
                               2 * x + dp[i - 3]));
    }
  
    // Last index represents the
    // minimum total cost
    document.write(dp[n - 1]);
}
 
// Driver code
 
// Given X
let X = 4;
 
// Given array cost[]
let cost = [ 6, 3, 9, 2, 1, 3 ];
 
let N = cost.length;
 
// Function Call
minimumCost(cost, N, X);
 
// This code is contributed by splevel62
 
</script>

Output

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

Efficient approach: Space Optimization O(1)

In previous approach the current value i.e. dp[i] is depend upon the previous three values i.e. dp[i-1] , dp[i-2] and dp[i-3]. So instead of using DP array we use variables to store these computation which will optimize the space complexity from O(N) to O(1).

Implementation Steps:

Implementation:

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 the array from
// the first element
void minimumCost(int* cost, int n, int x)
{ 
     // initialize varibles with base cases
    int prev1= cost[0]  , prev2=0, prev3=0 , curr=0;
      
      // iterate over subproblem 
    for (int i = 1; i < n; i++) {
          
          // if only 2 numbers we need only prev1 
        if (i == 1){
            curr = cost[i] + prev1;
              // get value of prev2
            prev2 = curr;
        }
           
          // get current value from prev2 and prev1
        if (i == 2){
            curr = cost[i]+ min(prev2,x + prev1);
              // get value of prev3
            prev3 = curr;
             
        }
          
          // get current value from prev3, prev2 and prev1
        if (i >= 3){
            curr = cost[i]+ min(prev3,min(x + prev2,2 * x + prev1));
           
          // assigning values to iterate further
            prev1 = prev2;
            prev2 = prev3;
            prev3 = curr;
        }
  
    }
      
      // curr represents the
    // minimum total cost
    cout << curr;
}
 
// Driver Code
int main()
{
    // Given X
    int X = 4;
 
    // Given array cost[]
    int cost[] = { 6, 3, 9, 2, 1, 3 };
 
    int N = sizeof(cost) / sizeof(cost[0]);
 
    // Function Call
    minimumCost(cost, N, X);
 
    return 0;
}
 
// this code is contributed by bhardwajji

Java

// Java program for the above approach
 
import java.util.*;
 
public class Main {
  // Function to find the minimum cost
// to reach the end of the array from
// the first element
static void minimumCost(int[] cost, int n, int x) {
    // initialize variables with base cases
    int prev1 = cost[0], prev2 = 0, prev3 = 0, curr = 0;
 
    // iterate over subproblem
    for (int i = 1; i < n; i++) {
        // if only 2 numbers we need only prev1
        if (i == 1) {
            curr = cost[i] + prev1;
            // get value of prev2
            prev2 = curr;
        }
 
        // get current value from prev2 and prev1
        if (i == 2) {
            curr = cost[i] + Math.min(prev2, x + prev1);
            // get value of prev3
            prev3 = curr;
 
        }
 
        // get current value from prev3, prev2 and prev1
        if (i >= 3) {
            curr = cost[i] + Math.min(prev3, Math.min(x + prev2, 2 * x + prev1));
 
            // assigning values to iterate further
            prev1 = prev2;
            prev2 = prev3;
            prev3 = curr;
        }
 
    }
 
    // curr represents the minimum total cost
    System.out.println(curr);
}
 
// Driver Code
public static void main(String[] args) {
    // Given X
    int X = 4;
 
    // Given array cost[]
    int[] cost = { 6, 3, 9, 2, 1, 3 };
 
    int N = cost.length;
 
    // Function Call
    minimumCost(cost, N, X);
}
}

Python3

# Python program for the above approach
 
def minimumCost(cost, n, x):
    # initialize variables with base cases
    prev1 = cost[0]
    prev2 = 0
    prev3 = 0
    curr = 0
 
    # iterate over subproblem
    for i in range(1, n):
        # if only 2 numbers we need only prev1
        if i == 1:
            curr = cost[i] + prev1
            # get value of prev2
            prev2 = curr
 
        # get current value from prev2 and prev1
        if i == 2:
            curr = cost[i] + min(prev2, x + prev1)
            # get value of prev3
            prev3 = curr
 
        # get current value from prev3, prev2 and prev1
        if i >= 3:
            curr = cost[i] + min(prev3, min(x + prev2, 2 * x + prev1))
 
            # assigning values to iterate further
            prev1, prev2, prev3 = prev2, prev3, curr
 
    # curr represents the minimum total cost
    print(curr)
 
 
# Driver Code
if __name__ == '__main__':
    # Given X
    X = 4
 
    # Given array cost[]
    cost = [6, 3, 9, 2, 1, 3]
 
    N = len(cost)
 
    # Function Call
    minimumCost(cost, N, X)

C#

using System;
 
class GFG {
    static void MinimumCost(int[] cost, int n, int x) {
        int prev1 = cost[0];
        int prev2 = 0;
        int prev3 = 0;
        int curr = 0;
        for (int i = 1; i < n; i++) {
            if (i == 1) {
                curr = cost[i] + prev1;
                prev2 = curr;
            }
            else if (i == 2) {
                curr = cost[i] + Math.Min(prev2, x + prev1);
                prev3 = curr;
            }
            else {
                curr = cost[i] + Math.Min(prev3, Math.Min(x + prev2, 2 * x + prev1));
                prev1 = prev2;
                prev2 = prev3;
                prev3 = curr;
            }
        }
        Console.WriteLine(curr);
    }
 
    static void Main() {
        int X = 4;
        int[] cost = new int[] {6, 3, 9, 2, 1, 3};
        int N = cost.Length;
        MinimumCost(cost, N, X);
    }
}

Javascript

// JavaScript program for the above approach
 
// Function to find the minimum cost
// to reach the end of the array from
// the first element
function minimumCost(cost, n, x) {
    // Initialize variables with base cases
    let prev1 = cost[0], prev2 = 0, prev3 = 0, curr = 0;
 
    // Iterate over subproblems
    for (let i = 1; i < n; i++) {
        // If there are only 2 numbers, we need only prev1
        if (i === 1) {
            curr = cost[i] + prev1;
            // Get the value of prev2
            prev2 = curr;
        }
 
        // Get the current value from prev2 and prev1
        if (i === 2) {
            curr = cost[i] + Math.min(prev2, x + prev1);
            // Get the value of prev3
            prev3 = curr;
        }
 
        // Get the current value from prev3, prev2, and prev1
        if (i >= 3) {
            curr = cost[i] + Math.min(prev3, Math.min(x + prev2, 2 * x + prev1));
 
            // Assigning values to iterate further
            prev1 = prev2;
            prev2 = prev3;
            prev3 = curr;
        }
    }
 
    // curr represents the minimum total cost
    console.log(curr);
}
 
// Driver Code
// Given X
const X = 4;
 
// Given array cost[]
const cost = [6, 3, 9, 2, 1, 3];
 
const N = cost.length;
 
// Function Call
minimumCost(cost, N, X);

Output

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

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!