Count number of paths in a grid using dynamic programming?

Question

A robot sitting on the upper left hand corner of an NxN grid. The robot can only move in two directions: right and down, Where some of cells are dead i.e. robot can't enter in that cell .How many possible paths are there for the robot?
This can be solved using Backtracking but it's time complexity is too high .I had solved this problem using backtracking but it takes O(2^n) in worse case .

bool exist(bool a[][], int i, int j,int N){
        return i>=0 && j >=0 && i < N && j < N;
    }
    int search(bool  a[][], int i, int j,int N){
        if(!exist(a,i,j,N) || a[i][j] == 1)
            return 0; // no path here.
        if(i == N-1 && j == N - 1){
            return 1; // 1 path here.
        }
        a[i][j] = 1; // mark that we have seen this spot here
        int paths = 0; // introduce a counter...
        paths += search(a, i,j+1,N); // add the additional paths as we find them
        paths += search(a, i+1,j,N);
        a[i][j] = 0;
        return paths; // return the number of paths available from this point.
    }

Here cell with 1 represents dead cell.Is any way to reduce time complexity by using DFS or Dynamic programming e.t.c ?

Answer 1

Given a NxN grid, let ways[i][j] = number of possible paths from grid[0][0] to grid[i][j]

initialize grid[0][0] = 1

if grid[i][j] is dead, ways[i][j] = 0

else ways[i][j] = ways[i-1][j] + ways[i][j-1] (but be careful with the edge)

An example:

grid:(1 means dead)   ways:

0 0 1 0 0             1 1 0 0 0
0 0 0 0 0             1 2 2 2 2
0 1 0 0 1             1 0 2 4 0
1 0 0 0 0             0 0 2 6 6
0 0 0 0 0             0 0 2 8 14

I think the complexity is O(n^2) since there n*n grids.