3 months ago

Suryansh Rishit • 0

Mysuru

Problem -2 

Approach / Logic

• Use recursive dynamic programming with memoization.

• Define a function solve(i) that returns the minimum cost to reach the last index starting from index i.

• Use a dp[] array to store the results for each index to avoid redundant calculations.

• At each index i, check all valid jumps (1 to 3 steps ahead), and take the minimum cost path.

Step-by-step Logic:

1. If i == n - 1, return 0 (we are already at the last index).

2. If dp[i] is already computed (≠ -1), return it.

3. Otherwise:

   • Try jumps of size 1, 2, and 3 (if i + jump < n)

   • For each valid jump, compute abs(arr[i] - arr[i + jump]) + solve(i + jump)

   • Take the minimum of these options

4. Store the result in dp[i] and return it.

Code:

#include<bits/stdc++.h>

using namespace std;

int solve(int i,vector<int> &arr,vector<int> &dp){
    int n = arr.size();
    if (i == n-1) return 0;
    int ans = INT_MAX;
    if (dp[i] != -1) return dp[i];
    if (i+1 < n){
        ans = min(ans,abs(arr[i]-arr[i+1])+solve(i+1,arr,dp));
    }
    if (i+2 < n){
        ans = min(ans,abs(arr[i]-arr[i+2])+solve(i+2,arr,dp));
    }
    if (i+3 < n){
        ans = min(ans,abs(arr[i]-arr[i+3])+solve(i+3,arr,dp));
    }
    return dp[i] = ans;

}

int main(){

    int n ;
    cin >> n;
    vector<int> arr(n);
    for(int i = 0 ; i < n;i++) cin >> arr[i];
    vector<int> dp(n,-1);
    cout << solve(0,arr,dp);


}

Time and Space Complexity

Time Complexity: O(n)

• Each index is visited only once and has at most 3 recursive calls.

• Memoization ensures that we don’t recompute values for the same index.

Space Complexity: O(n)

• dp[] takes O(n) space.

• Recursion stack in the worst case is O(n).