CODEWITHSUNDEEP
algorithmrecursioncoordinatesdynamic-programmingrandom-walk
natik
natik

Reputation: 21

Dynamic Programming - Given num K, how many ways to get from (0,0) to (x,y)?

A robot is moving in the (x~y) coordinate system according to a plan that was attached to him prior to his start. The robot always starts at (0, 0) and only understands 4 commands - WEST - (x-1, y) SUD - (x, y-1) OST - (x+1, y) NORD - (x, y+1) Every command lets the robot move one unit in the chosen direction. The robot's attached plan is made of a sequence of these commands.

Given a random coordinate for (x, y) and a natural number K, we want to calculate the number of different plans in the length of K that would bring the robot from (0, 0) to (x, y).

Aside of an explanation, I need an algorithm and the pseudo-code for it preferrably in C

So far, only thing I could think about is that the main condition would be that K cannot be smaller than abs(x+y), in this case i'd need to return 0 since there are zero sequences of K length that will get me to (x,y), or, more accurately, i'll never be able to get there with K steps.

Upvotes: 2

Views: 170

Answers (1)

Solomon Ucko
Solomon Ucko

Reputation: 6109

Use dynamic programming with the following observation: f(x, y, K) = f(x - 1, y, K - 1) + f(x + 1, y, K - 1) + f(x, y - 1, K - 1) + f(x, y + 1, K - 1)

Upvotes: 0

Related Questions