CODEWITHSUNDEEP
calgorithmrecursiondynamic-programming
MasterGL
MasterGL

Reputation: 111

How could you convert the following recursion with dynamic programming?

How would you convert the following recursive program with dynamic programming (DP)? I'm just having a little trouble trying to redefine this code into a dynamic programming form. I got the base case and the general case identified, and I am aware that DP is about a "bottom-up" approach.

int add(int, int);

int main()
{
    int x = 0, y = 0;
    printf("Enter positive integers x, y: ");
    scanf("%d %d", &x, &y);

    printf("Result: %d\n", add(x, y));

    return 0;
}

int add(int x, int y)
{
    if(x < 0 || y < 0){
        fprintf(stderr, "Negative Integer received!\n");
        return -1;
    }
    if (x == 1 || y == 1)
        return 1;
    else
        return add(x, y-1) + add(x - 1, y) + add(x-1, y-1);
}

Upvotes: 0

Views: 1256

Answers (2)

Eziz Durdyyev
Eziz Durdyyev

Reputation: 1158

Why do you want to do it in recursive way? There is an iterative way, and iterative 'almost always' beats recursive. Besides it is less code:

int DP[500][500];
memset(DP, 0, sizeof(DP));
for(int i=1; i<=x; i++) DP[i][1] = 1;
for(int i=1; i<=y; i++) DP[1][i] = 1;

for(int i=2; i<=x; i++) {
    for(int j=2; j<=y; j++) {
        DP[i][j] = DP[i-1][j-1] + DP[i-1][j] + DP[i][j-1];
    }
}

printf("Result: %d\n", DP[x][y]);

But if you insist on recursion you can pass your DP array to function by pointer. And every time check if you calculated DP[i][j] before, if so don't calculate it again and return back:

#include <stdio.h>
#include <string.h>

void add(int x, int y, int (*M)[500])
{
    if(M[x][y] > 0) return;

    if (x == 1 || y == 1) {
        M[x][y] = 1;
        return;
    }

    add(x, y-1, M);
    add(x - 1, y, M);
    add(x-1, y-1, M);

    M[x][y] = M[x][y-1] + M[x-1][y] + M[x-1][y-1];
    return;
}

int main()
{
    int x, y;
    printf("Enter x, y: ");
    scanf("%d %d", &x, &y);

    int DP[500][500];
    memset(DP, 0, sizeof(DP));
    add(x, y, DP);

    printf("Result: %d\n", DP[x][y]);

    return 0;
}

Upvotes: 1

Karnabanu Ashalagari
Karnabanu Ashalagari

Reputation: 61

Your code will cause stack overflow for all the possible x,y and z integer(negative, positive) combinations

Upvotes: 1

Related Questions