Dynamic Programming - Distinct Paths between two points - Techie Me
Count the number of distinct paths between two points on a two dimensional co-ordinate plain
We are given two points x1, y1 and x2, y2 on a two dimensional co-ordinate plain. The task at hand is to count the number of distinct paths from x1, y1 to x2, y2.
Assumption: x2 is greater than x1 and y2 is greater than y1.
Restriction: We can only move either up or right one step at a time, we cannot trace back or down.
Here is a diagram to explain the problem in more detail:
In the diagram above Point1 has co-ordinates (2,1) and Point2 has co-ordinates (4,2). We are at Point1 and we have to reach Point2. We have to find out the total number of distinct way from Point1 to Point2.
The three paths shown in the diagram are the only possible distinct paths. The three paths are painted in RED , GREEN and PURPLE.
How to mathematically solve it?
I would like to show the mathematical way of finding this, as per the restriction defined above we can move only one step at a time. We have to move two steps (x2 – x1) in the right and one step (y2 – y1) in the up direction.
This is a simple problem of counting where we have two similar steps to be taken one at a time in the right direction and one step in the up direction. This is as good as picking (a + b) objects where a objects are of one type and b object is of second type.
Read full article from Dynamic Programming - Distinct Paths between two points - Techie Me
No comments:
Post a Comment