I am in my early stages of learning dp <br>↵
Just wanted to know is it always possible to convert a dp solution into a recursive one<br>↵
If so can anyone write the recursive code for this dp solution<br>↵
↵
<spoiler summary="Spoiler">↵
... ↵
#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<long long int>↵
↵
#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;↵
↵
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,LLONG_MAX);↵
↵
dp[0]=0; ↵
↵
for(int i=1;i<=n;i++){↵
↵
dp[i]=min(dp[i-1]+1,dp[i]);↵
↵
if(i+v[i]<=n){↵
↵
dp[i+v[i]]=min(dp[i+v[i]],dp[i-1]);↵
↵
}↵
↵
if(i-v[i]>=1)dp[i]=min(dp[i],dp[i-v[i]-1]);↵
↵
}↵
↵
cout<<dp[n];↵
↵
nl;↵
↵
} ↵
↵
}↵
↵
</spoiler>↵
↵
<br>↵
The question is similar to [this](https://codeforces.com/problemset/problem/1741/E), 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
Just wanted to know is it always possible to convert a dp solution into a recursive one<br>↵
If so can anyone write the recursive code for this dp solution<br>↵
↵
<spoiler summary="Spoiler">↵
... ↵
#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<long long int>↵
↵
#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;↵
↵
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,LLONG_MAX);↵
↵
dp[0]=0; ↵
↵
for(int i=1;i<=n;i++){↵
↵
dp[i]=min(dp[i-1]+1,dp[i]);↵
↵
if(i+v[i]<=n){↵
↵
dp[i+v[i]]=min(dp[i+v[i]],dp[i-1]);↵
↵
}↵
↵
if(i-v[i]>=1)dp[i]=min(dp[i],dp[i-v[i]-1]);↵
↵
}↵
↵
cout<<dp[n];↵
↵
nl;↵
↵
} ↵
↵
}↵
↵
</spoiler>↵
↵
<br>↵
The question is similar to [this](https://codeforces.com/problemset/problem/1741/E), 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
