Can we do it without DP?

#1

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)

#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.

#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