00:00Now we are going to discuss a little trick, how we can solve the grid way in a math trick
00:04using linear time
00:07What time was going on? It was exponential time which is really huge
00:11But how we can decrease it in linear time using math formula
00:15If we have studied permutation, we need a little knowledge of permutation
00:21If we don't understand permutation, we can understand the last formula
00:25If we can write it in linear time, we can solve this problem
00:30If we ask in any contest or interview, we can solve it directly
00:35But there is no explanation, so we need to understand the explanation
00:38We will use permutation
00:40What can I say? If I am talking about any way or path
00:45Which I have used to go from this source to my target
00:49So in this path, n-1 will be right turns, down turns and m-1 will be right turns
01:01So if I am talking about a single path, which is right, right, down, down
01:05How will this path look? This path looks like right, right, down, down
01:10Or I am talking about another path, down, right, down, right
01:14So what can I say? Down, right, down, right
01:17So if I want to change my problem a little bit, I will make my problem
01:40So I have total characters, which will be equal to n-1 plus m-1
01:48I have so many characters
01:49And I have permutation for these characters
01:53I have permutation
01:54Permutation is
01:54If I have two d and two r
01:57Then I can arrange them in which way I can arrange them
02:00So permutation, I don't know how to get out of permutation
02:02First permutation is something like this
02:05Then permutation is something like this
02:07Then permutation is something like this
02:09Then permutation is something like this
02:10And this permutation is a single way
02:14It symbolizes a single way
02:15A single permutation means
02:17This is a way to go to the target
02:20If I am talking about DRRD
02:25This is a way to go to the destination
02:29So the problem is reduced to permutation
02:32Permutation problem is
02:33I have total characters
02:35How many characters are?
02:36n-1 plus m-1
02:38But there are some repeating characters
02:40What are repeating characters?
02:42One is n-1 repeating characters
02:45That means n-1 times
02:46I have d
02:47And one is m-1 repeating characters
02:49That means m-1 times
02:51I have r
02:52And what are the rules of permutation
02:53What are the rules of permutation?
02:55The rules of permutation
02:55They say
02:57If I have total number of permutation
02:58So that will be equal to
03:01n-1 plus m-1 factorial
03:04divided by repeating characters
03:07Repeating characters factorial
03:09n-1 factorial
03:10divided by m-1 factorial
03:13So if I have a simple formula
03:16This will be equal to my
03:19total ways
03:21In this way
03:22How much time will I take out of factorial?
03:24I take out of factorial
03:25I take out of factorial
03:26I take out of n-1
03:27So basically
03:28My time will be linear time
03:30Time will be reduced in which time
03:32Time will be big of n-1 plus m
03:34And this is a linear time
03:37For any algorithm
03:38If I take out of my 3 by 3 example
03:41Here
03:42What can I say
03:44For n is equal to 3
03:47And m is equal to 3
03:48Upers
03:493-1 plus 3-1
03:52Divided by 3-1 factorial
03:54Upers
03:56This will be equal to
04:04This will be equal to
04:054 into 3 into 2 into 1
04:07divided by 2 into 2
04:09This will be cut from this and I have 6
04:12So I have 6 ways in total
04:14For a 3 x 3 grid
04:17So when we have to use this
04:19We have seen the understanding of recursion and backtracking
04:23What will be the process
04:23But we can also use a direct mathematical formula
04:28Which is n-1 plus m-1 factorial
04:31Divided by n-1 factorial
04:33m-1 factorial