Difficulty in converting recursive solution to memoization / top-down DP

№	Пользователь	Рейтинг
1	jiangly	3640
2	Benq	3593
3	tourist	3572
4	orzdevinwang	3561
5	cnnfls_csy	3539
6	ecnerwala	3534
7	Radewoosh	3532
8	gyh20	3447
9	Rebelz	3409
10	Geothermal	3408

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
3	adamant	163
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	151
8	SecondThread	147
9	orz	146
10	pajenegod	145

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

Below is my Recursive Code to the problem:-

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;
}

It would be helpful if someone could suggest me some ideas on how to do so.

Комментарии (3)

Показать архивные | Написать комментарий?

Suri429

2 года назад, # |

One liner

Spoiler

Explanation

In your recursion, what is calculated first should be calculated first in here as well. When we call dp(0,n) in recursion ,(0,n) is calculated at the end, so even in for loops it should be calculated at the end. Now for this example Two variables, two loops, such that last state is 0,n

for loop decreasing to 0
   for loop increasing to n 
       Copy paste your recursion

→ Ответить

tfg

2 года назад, # ^ |

You didn't understand his problem. He's not asking how to code a bottom-up DP.

← Rev. 2 →

Got it. So @MoonKnight9031, I will give it another shot.. When you write recurrence, try to avoid including array/vector as a parameter to the recursive function(you can keep them globally) or let's ignore them for now. Now let's say your recursive function has k parameters, then initialize a table globally [][][].. k boxes. Size of ith box = number of different values ith parameter can have. Now you can fill your table with a value, which is a never possible value for any of your dp. Then you can have at start of recursion a check, if value exist in table return it else store value in table.

If you find that space is too much, maybe you need to rethink your recurrence or try to convert it to for loop dp as per my first comment and then use space optimization, if possible.

This submission will show you the whole process

143442881

Блог пользователя MoonKnight9031