## Interview Question

Applications Developers**Country:**United States

#include<stdio.h>

int count = 0;

void Recursion(int right, int down) {

if (right == 1 && down == 1) {

count++;

return;

}

if (down > 1){Recursion(right, down-1);}

if (right > 1){Recursion(right-1, down);}

return;

}

int main() {

int i = 0, m, n;

printf("Enter value of m & n: ");

scanf("%d %d", &m, &n);

Recursion(m, n);

printf("Count: %d", count);

return 0;

}

If the paths can only go down or right then straightforward dynamic programming can be used to solve the problem. To reach (y,x) you have to either reach (y-1,x) or (y,x-1) immediately prior; so the number of paths for these two sub-problems are added together.

This can be done either bottom up (with a table), or top down (with memoization and recursion).

- ZoeAcacia June 21, 2015