title: Calculating number of moves from top left corner to bottom right with move in any direction
body: <p>I have a problem asked to me in an interview, this is a similar problem I found so I thought of asking here. The problem is</p>
  
  <blockquote>
    <p>There is a robot situated at (1,1) in a N X N grid, the robot can move in any direction left, right ,up and down. Also I have been given an integer k, which denotes the maximum steps in the path. I had to calculate the number of possible ways to move from (1,1) to (N,N) in k or less steps.</p>
  </blockquote>
  
  <p>I know how to solve simplified version of this problem, the one with moves possible in only right and down direction. That can be solved with Dynamic Programming. I tried applying the same technique here but I don't think it could be solved using 2-dimensional matrix, I tried a similar approach counting possible number of ways from left or up or right and summing up in down direction, but the problem is I don't know number of ways from down direction which should also be added. So I go in a loop. I was able to solve this problem using recursion, I could recurse on (N,N,k) call for up, left and k-1, sum them up but I think this is also not correct, and if it could be correct it has exponential complexity. I found problems similar to this so I wanted to know what would be a perfect approach for solving these types of problems.</p>