In some Dynamic Programming Problems, I am able to code the recursive solution but I find it hard to convert it into Top-Down DP or Memoization. ↵
For example :- This is a problem from yesterday's Codechef Starters Contest:- [Problem Link](https://www.codechef.com/START23C/problems/MAXMINK)↵
↵
Below is my Recursive Code to the problem:-↵
↵
<spoiler summary="My Code">↵
~~~~~↵
//Coded By - Moon Knight↵
#include <bits/stdc++.h>↵
#define int long long↵
const int mod = 1000000007;↵
using namespace std;↵
↵
int helpera(int arr[], int n, vector<int> kk)↵
{↵
int sum = 0;↵
for (int i = 0; i < kk.size(); i++)↵
{↵
sum += arr[kk[i]];↵
}↵
return sum;↵
}↵
int solve(int arr[], int brr[], int n, int k, vector<int> kk, int i)↵
{↵
if (k==0 and i == n)↵
{↵
return min(helpera(arr, n, kk), helpera(brr, n, kk));↵
}↵
↵
if (k<0 or i>n)↵
{↵
return -1 * mod;↵
}↵
↵
int exc = solve(arr, brr, n, k, kk, i + 1);↵
↵
kk.push_back(i);↵
int inc = solve(arr, brr, n, k-1, kk, i + 1);↵
↵
return max(inc, exc);↵
}↵
↵
int32_t main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
cout.tie(NULL);↵
↵
int test;↵
cin >> test;↵
while (test--) {↵
↵
int n;↵
cin >> n;↵
int k;↵
cin >> k;↵
int arr[n];↵
int brr[n];↵
for (int i = 0; i < n; i++)↵
{↵
cin >> arr[i];↵
}↵
↵
for (int i = 0; i < n; i++)↵
{↵
cin >> brr[i];↵
}↵
vector<int> kk;↵
cout << solve(arr, brr, n, k, kk, 0) << endl;↵
↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
It would be helpful if someone could suggest me some ideas on how to do so.↵
For example :- This is a problem from yesterday's Codechef Starters Contest:- [Problem Link](https://www.codechef.com/START23C/problems/MAXMINK)↵
↵
Below is my Recursive Code to the problem:-↵
↵
<spoiler summary="My Code">↵
~~~~~↵
//Coded By - Moon Knight↵
#include <bits/stdc++.h>↵
#define int long long↵
const int mod = 1000000007;↵
using namespace std;↵
↵
int helpera(int arr[], int n, vector<int> kk)↵
{↵
int sum = 0;↵
for (int i = 0; i < kk.size(); i++)↵
{↵
sum += arr[kk[i]];↵
}↵
return sum;↵
}↵
int solve(int arr[], int brr[], int n, int k, vector<int> kk, int i)↵
{↵
if (k==0 and i == n)↵
{↵
return min(helpera(arr, n, kk), helpera(brr, n, kk));↵
}↵
↵
if (k<0 or i>n)↵
{↵
return -1 * mod;↵
}↵
↵
int exc = solve(arr, brr, n, k, kk, i + 1);↵
↵
kk.push_back(i);↵
int inc = solve(arr, brr, n, k-1, kk, i + 1);↵
↵
return max(inc, exc);↵
}↵
↵
int32_t main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
cout.tie(NULL);↵
↵
int test;↵
cin >> test;↵
while (test--) {↵
↵
int n;↵
cin >> n;↵
int k;↵
cin >> k;↵
int arr[n];↵
int brr[n];↵
for (int i = 0; i < n; i++)↵
{↵
cin >> arr[i];↵
}↵
↵
for (int i = 0; i < n; i++)↵
{↵
cin >> brr[i];↵
}↵
vector<int> kk;↵
cout << solve(arr, brr, n, k, kk, 0) << endl;↵
↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
It would be helpful if someone could suggest me some ideas on how to do so.↵
