• + 0 comments

    Reference Table

    [Edit] Notice how each column below the pivot (row1, col1 -> row2 col2 ->etc) contains the same pattern (0, 1, 1, 2, 2, 1, 2, 2, 3, 3, etc) . This pattern is the number of minimum steps to reduce the row value (arr[i]) to the column value (min).

    Because of this in my final approach, I've decided to use only column 0 as my memoization array, called grid, since I can use index manipulation to fetch the result. For example:

    1 . 4 . 2 2 3 7

    if I wanted to find the minimum number of steps to go from 7 to 2, it would be 1 step of (-5), but instead of returning grid.at(7), i'll return grid.at(7 - min).

    The cycle repeats 4 more times with each cycle decrementing the minimum value by 1, even below 0 - in which case row (7 - min) would still be in the grid.

    A similar problem is TheCoinChangeProblem. If you can solve that one, then you'll see the process I found in this one.