GoldMan Sachs | SDE | OA | CTC - 30 Lac | 2023 | DP

Question

An array of costs was given. 
You always start at index 1. 
You can either take two jumps forward or one jump backward. If you land on a particular index, you have to add the cost to your total. 
Find the minimum cost needed to cross the array or reach the end of the array.
You can visit any index for only 1 time. 

b = [ 2 5 8 ] 

cost = 10 

Comments

#include <bits/stdc++.h>
using namespace std;
#define int long long
//f(i):i se end tak ka  cost
//f(i)=min(f(i+2)+a[i+2],f(i+1)+a[i-1]+a[i+2])


int32_t main() {
    int n;
    cin>>n;
    vector<int>vec(n);
    for(int i=0;i<n;i++)
    cin>>vec[i];
    vector<int>dp(n+1,INT_MAX);
    dp[n-1]=vec[n-1];
    for(int i=n-1;i>=0;i--){
        if(i+2<n)
        dp[i]=min(vec[i]+dp[i+2],vec[i]+vec[i+2]+dp[i+1]);
    }
    for(int i=0;i<n;i++)
    cout<<dp[i]<<" ";
    return 0;
}


please check this if it works

Answer 1

#include <bits/stdc++.h>

 

using namespace std;

#define int long long

#define endl '\n'

 

void solve()

{

 

    int n;

    cin >> n;

 

    vector<int> a(n + 1);

    for (int i = 1; i <= n; i++)

        cin >> a[i];

 

    vector<vector<int>> dp(n + 1, vector<int>(3, 1e9));

 

    dp[1][2] = a[1];

    dp[2][1] = dp[1][2] + a[2] + a[3];

 

    for (int i = 3; i <= n - 1; i++)

    {

        dp[i][2] = a[i] + min(dp[i - 2][1], dp[i - 2][2]);

        dp[i][1] = a[i + 1] + a[i] + dp[i - 1][2];

    }

 

    dp[n][2] = a[n] + min(dp[n - 2][1], dp[n - 2][2]);

 

    cout << min(dp[n][2], min(dp[n - 1][1], dp[n - 1][2]));

}

 

signed main()

{

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

 

    solve();

 

    return 0;

}

Answer 2

#include <bits/stdc++.h>
using namespace std;
#define int long long

int32_t main() {
    int n;
    cin>>n;
    vector<int>vec(n);
    for(int i=0;i<n;i++)
    cin>>vec[i];
    vector<int>dp(n+1,INT_MAX);
    dp[n-1]=vec[n-1];
    for(int i=n-1;i>=0;i--){
        if(i+2<n)
        dp[i]=min(vec[i]+dp[i+2],vec[i]+vec[i+2]+dp[i+1]);
    }
    for(int i=0;i<n;i++)
    cout<<dp[i]<<" ";
    return 0;
}