ayush118's blog

Need help in converting dp solution to a recursive one
By ayush118, history, 2 days ago, In English

I am in my early stages of learning dp
Just wanted to know is it always possible to convert a dp solution into a recursive one
If so can anyone write the recursive code for this dp solution

Spoiler


The question is similar to this, the only difference is that we have to find the minimum elements to remove from the sequence b so that it can be sent over the network

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ayush118 (previous revision, new revision, compare).

→ Reply
»
36 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Here's your recursive solution

#include <bits/stdc++.h>

#define lli long long int

#define pii pair<int, int>

#define mii map<int, int>

#define vi vector<int>

#define pb push_back

#define vlli vector

#define nl cout << '\n'

#define yy cout << "YES\n"

#define nn cout << "NO\n"

#define all(a) a.begin(), a.end()

#define IM INT_MAX

#define IMN INT_MIN

#define pc cout << count << '\n'

#define int long long int

#define mp make_pair

#define vpii vector<pair<int, int>>

#define Yy cout << "Yes\n"

#define Nn cout << "No\n"

using namespace std;


int helper(vector<int> &v, int i, vector<int> &dp){
    if(i==v.size())  return 0;
    if(dp[i]!=-1)  return dp[i];

    dp[i]=1e9;
    dp[i]=min(helper(v, i+1, dp)+1, dp[i]);
    if(v[i]+i<=v.size())  dp[i]=min(dp[i], helper(v, i+v[i]+1, dp));
    if(i-v[i]>=1)  dp[i-v[i]]=min(dp[i-v[i]], helper(v, i+1, dp));
    return dp[i];
}
signed main()
{

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    int t;
    cin >> t;

    while (t--)
    {

        int n;
        cin >> n;

        vi v;

        v.pb(0);

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

            int x;
            cin >> x;

            v.pb(x);
        }

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

        cout<<helper(v, 1, dp)<<"\n";
    }
}
→ Reply