We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
[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.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Equal
You are viewing a single comment's thread. Return to all 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.