Given two arrays A[] and B[] of N positive integers and a cost C. We can choose any one element from each index of the given arrays i.e., for any index i we can choose only element A[i] or B[i]. The task is to find the minimum total sum of selecting N elements from the given two arrays and if we are selecting any element from A[] to B[] or vice-versa in the next iteration then the cost C is also added to the sum.
Note: Choose element in increasing order of index i.e., 0 ? i < N.
Examples:
Input: N = 9, A[] = {7, 6, 18, 6, 16, 18, 1, 17, 17}, B[] = {6, 9, 3, 10, 9, 1, 10, 1, 5}, C = 2
Output: 49
Explanation:
On taking the 1st element from array A, sum = 7
On taking the 2nd element from array A, sum = 7 + 6 = 13
On taking the 3rd element from array B, as we are entering from array A to array B, sum = 13 + 3 + 2 = 18
On taking the 4th element from array A, as we are entering from array B to array A, sum = 18 + 6 + 2 = 26
On taking the 5th element from array B, as we are entering from array A to array B, sum = 26 + 9 + 2 = 37
On taking the 6th element form array B, sum = 37 + 1 = 38
On taking the 7th element from array A, as we are entering from array B to array A, sum = 38 + 1 + 2 = 41
On taking the 8th element form array B, as we are entering from array A to array B, sum = 41 + 1 + 2 = 44
On taking the 9th element from array B, sum = 44 + 5 = 49.Input: N = 9, A = {3, 2, 3, 1, 3, 3, 1, 4, 1}, B = {1, 2, 3, 4, 4, 1, 2, 1, 3}, C = 1
Output: 18
Explanation:
On taking the 1st element from array B, sum = 1
On taking the 2nd element from array A, sum = 1 + 2 = 3
On taking the 3rd element from array A, sum = 3 + 3 = 6
On taking the 4th element from array A, sum = 6 + 1 = 7
On taking the 5th element from array A, sum = 7 + 3 = 10
On taking the 6th element form array B, as we are entering from array A to array B, sum = 10 + 1 + 1 = 12
On taking the 7th element from array A, as we are entering from array B to array A, sum = 12 + 1 + 1 = 14
On taking the 8th element form array B, as we are entering from array A to array B, sum = 14 + 1 + 1 = 16
On taking the 9th element from array A, as we are entering from array B to array A, sum = 16 + 1 + 1 = 18.
Approach: We will use Dynamic Programming to solve this problem. Below are the steps:
- Create a 2D array dp[][] of N rows and two columns and initialize all elements of dp to infinity.
- There can be 4 possible cases of adding the elements from both the arrays:
- Adding an element from array a[] when the previously added element is from array a[].
- Adding an element from array a[] when the previously added element is from array b[]. In this case there is a penalty of adding the integer C with the result.
- Adding an element from array b[] when the previously added element is from array b[].
- Adding an element from array b[] when the previously added element is from array a[]. In this case there is a penalty of adding the integer C with the result.
- Update the dp array each time with the minimum value of the above four conditions.
- The minimum of dp[n-1][0] and dp[n-1][1] is the total minimum sum of selecting N elements.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function that prints minimum sum // after selecting N elements void minimumSum(int a[], int b[], int c, int n) { // Initialise the dp array vector<vector<int> > dp(n, vector<int>(2, 1e6)); // Base Case dp[0][0] = a[0]; dp[0][1] = b[0]; for (int i = 1; i < n; i++) { // Adding the element of array a if // previous element is also from array a dp[i][0] = min(dp[i][0], dp[i - 1][0] + a[i]); // Adding the element of array a if // previous element is from array b dp[i][0] = min(dp[i][0], dp[i - 1][1] + a[i] + c); // Adding the element of array b if // previous element is from array a // with an extra penalty of integer C dp[i][1] = min(dp[i][1], dp[i - 1][0] + b[i] + c); // Adding the element of array b if // previous element is also from array b dp[i][1] = min(dp[i][1], dp[i - 1][1] + b[i]); } // Print the minimum sum cout << min(dp[n - 1][0], dp[n - 1][1]) << "\n"; } // Driver Code int main() { // Given array arr1[] and arr2[] int arr1[] = { 7, 6, 18, 6, 16, 18, 1, 17, 17 }; int arr2[] = { 6, 9, 3, 10, 9, 1, 10, 1, 5 }; // Given cost int C = 2; int N = sizeof(arr1) / sizeof(arr1[0]); // Function Call minimumSum(arr1, arr2, C, N); return 0; } |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function that prints minimum sum// after selecting N elementsstatic void minimumSum(int a[], int b[], int c, int n){ // Initialise the dp array int [][]dp = new int[n][2]; for(int i = 0; i < n; i++) { for(int j = 0; j < 2; j++) { dp[i][j] = (int) 1e6; } } // Base Case dp[0][0] = a[0]; dp[0][1] = b[0]; for(int i = 1; i < n; i++) { // Adding the element of array a if // previous element is also from array a dp[i][0] = Math.min(dp[i][0], dp[i - 1][0] + a[i]); // Adding the element of array a if // previous element is from array b dp[i][0] = Math.min(dp[i][0], dp[i - 1][1] + a[i] + c); // Adding the element of array b if // previous element is from array a // with an extra penalty of integer C dp[i][1] = Math.min(dp[i][1], dp[i - 1][0] + b[i] + c); // Adding the element of array b if // previous element is also from array b dp[i][1] = Math.min(dp[i][1], dp[i - 1][1] + b[i]); } // Print the minimum sum System.out.print(Math.min(dp[n - 1][0], dp[n - 1][1]) + "\n");}// Driver Codepublic static void main(String[] args){ // Given array arr1[] and arr2[] int arr1[] = { 7, 6, 18, 6, 16, 18, 1, 17, 17 }; int arr2[] = { 6, 9, 3, 10, 9, 1, 10, 1, 5 }; // Given cost int C = 2; int N = arr1.length; // Function call minimumSum(arr1, arr2, C, N);}}// This code is contributed by gauravrajput1 |
Python3
# Python3 program for the above approach # Function that prints minimum sum # after selecting N elements def minimumSum(a, b, c, n): # Initialise the dp array dp = [[1e6 for i in range(2)] for j in range(n)] # Base Case dp[0][0] = a[0] dp[0][1] = b[0] for i in range(1, n): # Adding the element of array a if # previous element is also from array a dp[i][0] = min(dp[i][0], dp[i - 1][0] + a[i]) # Adding the element of array a if # previous element is from array b dp[i][0] = min(dp[i][0], dp[i - 1][1] + a[i] + c) # Adding the element of array b if # previous element is from array a # with an extra penalty of integer C dp[i][1] = min(dp[i][1], dp[i - 1][0] + b[i] + c) # Adding the element of array b if # previous element is also from array b dp[i][1] = min(dp[i][1], dp[i - 1][1] + b[i]) # Print the minimum sum print(min(dp[n - 1][0], dp[n - 1][1])) # Driver code if __name__ == '__main__': # Given array arr[] arr1 = [ 7, 6, 18, 6, 16, 18, 1, 17, 17 ] arr2 = [ 6, 9, 3, 10, 9, 1, 10, 1, 5 ] # Given cost C = 2 N = len(arr1) # Function Call minimumSum(arr1, arr2, C, N) # This code is contributed by Shivam Singh |
C#
// C# program for the above approachusing System;class GFG{// Function that prints minimum sum// after selecting N elementsstatic void minimumSum(int []a, int []b, int c, int n){ // Initialise the dp array int [,]dp = new int[n, 2]; for(int i = 0; i < n; i++) { for(int j = 0; j < 2; j++) { dp[i, j] = (int)1e6; } } // Base Case dp[0, 0] = a[0]; dp[0, 1] = b[0]; for(int i = 1; i < n; i++) { // Adding the element of array a if // previous element is also from array a dp[i, 0] = Math.Min(dp[i, 0], dp[i - 1, 0] + a[i]); // Adding the element of array a if // previous element is from array b dp[i, 0] = Math.Min(dp[i, 0], dp[i - 1, 1] + a[i] + c); // Adding the element of array b if // previous element is from array a // with an extra penalty of integer C dp[i, 1] = Math.Min(dp[i, 1], dp[i - 1, 0] + b[i] + c); // Adding the element of array b if // previous element is also from array b dp[i, 1] = Math.Min(dp[i, 1], dp[i - 1, 1] + b[i]); } // Print the minimum sum Console.Write(Math.Min(dp[n - 1, 0], dp[n - 1, 1]) + "\n");}// Driver Codepublic static void Main(String[] args){ // Given array arr1[] and arr2[] int []arr1 = { 7, 6, 18, 6, 16, 18, 1, 17, 17 }; int []arr2 = { 6, 9, 3, 10, 9, 1, 10, 1, 5 }; // Given cost int C = 2; int N = arr1.Length; // Function call minimumSum(arr1, arr2, C, N);}}// This code is contributed by Rajput-Ji |
Javascript
<script>// JavaScript program for the above approach// Function that prints minimum sum// after selecting N elementsfunction minimumSum(a, b, c, n){ // Initialise the dp array let dp = new Array(n); for (var i = 0; i < dp.length; i++) { dp[i] = new Array(2); } for(let i = 0; i < n; i++) { for(let j = 0; j < 2; j++) { dp[i][j] = 1e6; } } // Base Case dp[0][0] = a[0]; dp[0][1] = b[0]; for(let i = 1; i < n; i++) { // Adding the element of array a if // previous element is also from array a dp[i][0] = Math.min(dp[i][0], dp[i - 1][0] + a[i]); // Adding the element of array a if // previous element is from array b dp[i][0] = Math.min(dp[i][0], dp[i - 1][1] + a[i] + c); // Adding the element of array b if // previous element is from array a // with an extra penalty of integer C dp[i][1] = Math.min(dp[i][1], dp[i - 1][0] + b[i] + c); // Adding the element of array b if // previous element is also from array b dp[i][1] = Math.min(dp[i][1], dp[i - 1][1] + b[i]); } // Print the minimum sum document.write(Math.min(dp[n - 1][0], dp[n - 1][1]) + "<br/>");}// Driver Code // Given array arr1[] and arr2[] let arr1 = [ 7, 6, 18, 6, 16, 18, 1, 17, 17 ]; let arr2 = [ 6, 9, 3, 10, 9, 1, 10, 1, 5 ]; // Given cost let C = 2; let N = arr1.length; // Function call minimumSum(arr1, arr2, C, N);</script> |
49
Time Complexity: O(N), where N is the size of the given array.
Auxiliary Space: O(N), for creating additional dp array.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
