Interview Question for Software Engineering Intern at Google:

Apr 18, 2012

Classic recursion problem:

int CalcPaths(int nXPos, int nYPos, int M, int N)
{
    if(nXPos > M || nYPos > N)
    {
        return 0;
    }

    if(nXPos == M && nYPos == N)
    {
        return 1;
    }

    return CalcPaths(nXPos+1, nYPos, M, N) + CalcPaths(nXPos, nYPos + 1, M, N);
}

Use dynamic programming to process the problem bottom up, that will significantly reduce the redundant computation effort. The basic idea is same as the recursive method.