読者です 読者をやめる 読者になる 読者になる

Robot is moving in grid

Dynamic Programming Recurrence Relation Recursive Cracking The Coding Interview

Problem

Imagine a robot sitting on the upper left corner of an X by Y grid. The robot can only move in two directions: right and down. How many possible paths are there for the robot to go from (0, 0) to (X, Y)?

How to Solve

By using Dynamic Programming, we can solve this problem efficiently. First we can make recurrence relation like this.

memo(i, j) = memo(i - 1, j) + memo(i, j -1)

memo(i, j) is defined that the count of paths from coordinate(i, j) to (X, Y).