i submitted it successfully using dp,it took too much time to think this way,is there any way we can do it without dp?

all i know is total i+j=10;(in every path)

# Can we do it without DP?

**CepGamer**#2

Yes, it’s possible. This sequence is essentially a Pascal’s triangle so you can use combination formula to calculate it. Though be careful since factorial calculation can overflow real fast.

**seedship**#3

```
class Solution:
# @param A : integer
# @param B : integer
# @return an integer
def uniquePaths(self, A, B):
return math.factorial(A + B - 2) // math.factorial(A - 1) // math.factorial(B - 1)
```

This is how I did it with Python3. You can think of it as asking, how many ways are there to form a sequence of A-1 R’s (Right) and B-1 D’s (Down). Thus, the formula for number of ways to form a word with letters is

length! / (letterA! * letterB! * letterC! * … ) https://math.stackexchange.com/questions/236471/how-many-ways-can-the-letters-in-arrangement-can-be-arranged