Finding the minimum steps to reach {m,n} in the grid [reviewed]

Problem

A robot has to move in a grid which is in the form of a matrix. It can go to 

1.) A(i,j) --> A(i+j,j) (Down) 

2.) A(i,j)-->A(i,i+j) (Right) 

Given it starts at (1,1) and it has to go to A(m,n), find the minimum number of STEPS it has to take to get to (m,n) and write 

public static int minSteps(int m,int n) 

For instance to go from (1,1) to m=3 and n=2 it has to take (1, 1) ->(1, 2) ->(3, 2) i.e. 2 steps

At first glance, it seems that it is a typical dynamic programming problem. It looks so especially because of this phrase "find the minimum number of STEPS". This is a trap.

If you think that there is multiple ways to get from (1,1) to (3,2), try to go backward from (3, 2) to (1,1) and see how ways exists. Let's try that manually.

1. From (3, 2),  (1, 2) is only prior step since down move results in bigger m values than n value.

2, From (1, 2),  (1,1) is the only prior step since only right move results in bigger n value than m value.

There is no other ways !!.

Therefore, we just trace back from (m, n) to (1,1) by checking each time whether it was from up or left position.


Here is the complete code in c++.



Practice statistics

12:00: misunderstood the question and got it wrong.  Later rewrote the code after understanding the question correctly.


UPDATE(2019-08-08): solved the problem again. Totally fooled by the word "minimum steps". There can be only one path exists. No multiple path !!


Practice statistics

1:14:56: to write the wrong dynamic programming code and rewrote the code after finding out the trick in the question.