Minimum Possible Cost of Flight ticket required to reach the city D
Given two integers N, D and an array A[] of size N where A[i] represents the population of ith city. For any city i, there are two flights to city (i+1) and to city (i+3), if they exist and the cost of a flight ticket between any two cities is the absolute difference between the population of those cities. Find the minimum cost to reach the Dth city.
Note: We can start from the 0th city or the 2nd city only.
Examples:
Input: N = 4, A[] = [1, 4, 5, 2], D = 3
Output: 1
Explanation: To reach the 3rd city, we have these options:
- Start from the 0th city, move to the first city, then to the 2nd city and finally to the 3rd city, so cost = |1 β 4| + |4 β 5| + |5 β 2| = 3 + 1 + 3 = 7
- Start from the 0th city and move to the 3rd city, so cost = |2 β 1| = 1
- Start from the 2nd city and move to the 3rd city, so cost = |5 β 2| = 3
The minimum cost to reach the 3rd city is 1
Input: N = 5, A = [3, 7, 2], D = 2
Output: 0
Explanation: To reach the 2nd city, we have these options:
- Start from the 0th city, move to the 1st city and then move to the 2nd city, so cost = |3 β 7| + |7 β 2| = 4 + 5 = 9
- Start from the 2nd city, so cost = 0
The minimum cost to reach 2nd city is 0
Approach: The problem can be solved using the following approach:
We can solve the problem using Dynamic Programming because of overlapping subproblems and optimal substructure. We need to have a dp[] array where dp[i] will store the minimum cost to reach ith city. Then for every index i, we will calculate the cost to reach ith city by using dp[i-1] and dp[i-3]. For cities having index smaller than 3, we can calculate their answer separately.
Below are the steps involved in the approach:
- Maintain a dynamic programming (DP) array dp of size D+1 to store the minimum costs.
- Initialize dp[0] and dp[2] as 0.
- Initialize dp[1] as abs(A[0] β A[1]).
- Iterate over the cities from the 3rd city to the Dth city:
- For each city at index i, calculate the total cost of flying from the previous city (index i-1) to the current city (index i) and store it in dp[i].
- Check if we can achieve a better cost by flying from the city i-3 (if i is greater than or equal to 3) to the current city. Update dp[i] if this cost is smaller than the previously calculated cost.
- The final answer is stored in dp[D], which represents the minimum cost to reach the Dth city.
C++
#include <iostream> #include <vector> using namespace std; int minimumCostToReachCityN(vector< int >& A, int N, int D) { // Initialize an array to store minimum costs vector< int > dp(D + 1, 1000000000); dp[0] = 0; if (D > 0) { dp[1] = abs (A[0] - A[1]); } if (D > 1) { dp[2] = 0; } // Iterate through cities from the 3rd city // to the D-th city. for ( int i = 3; i <= D; i++) { // Flying directly from the previous // city (i-1) to the current city (i). dp[i] = dp[i - 1] + abs (A[i] - A[i - 1]); // Calculate the cost of flying from the // city three steps back (i-3) to // the current city (i). dp[i] = min(dp[i], dp[i - 3] + abs (A[i] - A[i - 3])); } return dp[D]; } int main() { int N = 4; int D = 3; vector< int > A = {1, 4, 5, 2}; int result = minimumCostToReachCityN(A, N, D); // Function Call cout << result << endl; return 0; } |
Java
// Java Code for the above approach import java.util.Arrays; public class MinimumCostToReachCityN { public static int minimumCostToReachCityN( int [] A, int N, int D) { // Initialize an array to store minimum costs int [] dp = new int [D + 1 ]; Arrays.fill(dp, 1000000000 ); dp[ 0 ] = 0 ; if (D > 0 ) { dp[ 1 ] = Math.abs(A[ 0 ] - A[ 1 ]); } if (D > 1 ) { dp[ 2 ] = 0 ; } // Iterate through cities from the 3rd city // to the D-th city. for ( int i = 3 ; i <= D; i++) { // Flying directly from the previous // city (i-1) to the current city (i). dp[i] = dp[i - 1 ] + Math.abs(A[i] - A[i - 1 ]); // Calculate the cost of flying from the // city three steps back (i-3) to // the current city (i). dp[i] = Math.min(dp[i], dp[i - 3 ] + Math.abs(A[i] - A[i - 3 ])); } return dp[D]; } public static void main(String[] args) { int N = 4 ; int D = 3 ; int [] A = { 1 , 4 , 5 , 2 }; int result = minimumCostToReachCityN(A, N, D); // Function Call System.out.println(result); } } |
Python3
# Python Code for the above approach def minimumCostToReachCityN(A, N, D): # Initialize an array to store minimum costs dp = [ 1000000000 ] * (D + 1 ) dp[ 0 ] = 0 if D > 0 : dp[ 1 ] = abs (A[ 0 ] - A[ 1 ]) if D > 1 : dp[ 2 ] = 0 # Iterate through cities from the 3rd city # to the D-th city. for i in range ( 3 , D + 1 ): # Flying directly from the previous # city (i-1) to the current city (i). dp[i] = dp[i - 1 ] + abs (A[i] - A[i - 1 ]) # Calculate the cost of flying from the # city three steps back (i-3) to # the current city (i). dp[i] = min (dp[i], dp[i - 3 ] + abs (A[i] - A[i - 3 ])) return dp[D] # Example usage: N = 4 D = 3 A = [ 1 , 4 , 5 , 2 ] result = minimumCostToReachCityN(A, N, D) # Function Call print (result) |
C#
using System; public class GFG { public static int MinimumCostToReachCityN( int [] A, int N, int D) { // Initialize an array to store minimum costs int [] dp = new int [D + 1]; for ( int i = 0; i <= D; i++) { dp[i] = 1000000000; } dp[0] = 0; if (D > 0) { dp[1] = Math.Abs(A[0] - A[1]); } if (D > 1) { dp[2] = 0; } // Iterate through cities from the 3rd city // to the D-th city. for ( int i = 3; i <= D; i++) { // Flying directly from the previous // city (i-1) to the current city (i). dp[i] = dp[i - 1] + Math.Abs(A[i] - A[i - 1]); // Calculate the cost of flying from the // city three steps back (i-3) to // the current city (i). dp[i] = Math.Min( dp[i], dp[i - 3] + Math.Abs(A[i] - A[i - 3])); } return dp[D]; } public static void Main( string [] args) { int N = 4; int D = 3; int [] A = { 1, 4, 5, 2 }; int result = MinimumCostToReachCityN(A, N, D); // Function Call Console.WriteLine(result); } } // This code is contributed by Rohit Singh |
Javascript
// JavaScript Code for the above approach function minimumCostToReachCityN(A, N, D) { // Initialize an array to store minimum costs const dp = new Array(D + 1).fill(1000000000); dp[0] = 0; if (D > 0) { dp[1] = Math.abs(A[0] - A[1]); } if (D > 1) { dp[2] = 0; } // Iterate through cities from the 3rd city // to the D-th city. for (let i = 3; i <= D; i++) { // Flying directly from the previous // city (i-1) to the current city (i). dp[i] = dp[i - 1] + Math.abs(A[i] - A[i - 1]); // Calculate the cost of flying from the // city three steps back (i-3) to // the current city (i). dp[i] = Math.min(dp[i], dp[i - 3] + Math.abs(A[i] - A[i - 3])); } return dp[D]; } // Example usage: const N = 4; const D = 3; const A = [1, 4, 5, 2]; const result = minimumCostToReachCityN(A, N, D); // Function Call console.log(result); |
1
Time Complexity: O(N), where N is the index of city whose minimum cost is needed.
Auxiliary Space: O(N)