In Dynamic Programming Problems, I am easily able to make the recursive solutions but I am unable to convert it into memoization/dynamic programming. This is a question from yesterday’s Starters. The backtracking code is giving correct answer.
//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;
}
QuestionProblem Link Link.
It would be helpful if someone could convert this into a memoized DP with minimal changes and also instruct on how to do so.