count number of uniq paths in maze

Question

I know the backtracking approach to count path [0,0] to [n,n] in matrix. but not able to solve it by dynamic programming. Is it even possible without backtracking ??

you can move only right or down

1 1 1 1
1 0 1 1
1 1 0 1
1 1 1 1
`

number of path to reach from top left to bottom right is 4

Answer 1

Yep. Say p(i,j) is the number of partial paths to i,j. If we're using zero-indexing then what you want is p(n-1,n-1). What you know is that p(0,0)=1, also p(i,j) is the sum of the value to the left if you can travel from p(i-1,j) to p(i,j), and the value above if you can travel from p(i,j-1) to p(i,j).

So you use all that to fill out a matrix. Pretty much that's what DP is: matrix-filling. Once you figure out how to fill out the matrix you're done.