[Solved] There are N cities in a country. George is initially at the airport in city 1 and he wants to reach city N.C++,Java, Python

There are N cities in a country. George is initially at the airport in city 1 and he wants to reach city N. For any city i, there is either a flight to city (i+1) or to (i+3) if it exists. You have been given an array A with the costs of flight tickets for N cities. To find the cost of a flight ticket between any two cities i and j, you take the absolute difference of the costs of those cities in the array A. You can use the formula |a| = |Cost[i] – Cost[j]| to calculate the cost of a flight ticket, where |a| represents the absolute value of a. Your task is to find and return the minimum possible cost of flight ticket required to reach the city N. Note: The number of cities is always greater than 3. Assume 1 based indexing. Input Specification: input1 : An integer value N, representing the number of cities. input2 : An integer array A, representing the cost of tickets to reach the ith a city. Output Specification: Return the minimum possible cost of flight ticket required to reach the city N.

Example 1: input1 : 4 input2 : {1,4,5,2} Output : 1 Explanation: George takes a flight in the below optimal manner: From city 1 to city 4 , as city 4 is the third next city to city 1 so the cost will be |1-2| = 1. Hence, 1 is returned as the output. Example 2: input1 : 6 input2 : {4,12,13,18,10,12} Output : 10 Explanation: George takes a flight in the below optimal manner: From city 1 to city 2, the cost will be |4-12| = 8 From city 2 to city 3, the cost will be |12-13| = 1 From city 3 to city 6, the cost will be |13-12| = 1 . Write code in cpp

Solution

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int minFlightCost(int N, vector<int>& A) {
    vector<int> dp(N + 1, 0);

    // Initialize the dynamic programming array
    dp[1] = 0;
    dp[2] = abs(A[1] - A[2]);
    dp[3] = min(abs(A[1] - A[3]), abs(A[2] - A[3]));

    // Calculate the minimum cost using dynamic programming
    for (int i = 4; i <= N; ++i) {
        dp[i] = min(dp[i - 1] + abs(A[i - 1] - A[i]), dp[i - 3] + abs(A[i - 3] - A[i]));
    }

    return dp[N];
}

int main() {
    // Input
    int N1 = 4;
    vector<int> A1 = {1, 4, 5, 2};

    int N2 = 6;
    vector<int> A2 = {4, 12, 13, 18, 10, 12};

    // Output
    int output1 = minFlightCost(N1, A1);
    int output2 = minFlightCost(N2, A2);

    // Print Output
    cout << "Output 1: " << output1 << endl;  // Output: 1
    cout << "Output 2: " << output2 << endl;  // Output: 10

    return 0;
}

Happy Learning – If you require any further information, feel free to contact me.