title: Robot Motion - Dynamic Programming
body: <p>Given a 1D world of infinite length (x),
  and available moves (y) of, for example [1, 2, 3, -1, -2, -3],
  and a destination (d) (ie 15), write a function that returns
  the smallest number of moves (result) needed to reach d.</p>
  
  <p>For example if d = 15, result = 5
  since the most optimal move is 3, and it can be done 5 times.</p>
  
  <p>This problem is very similar to this: <a href="https://www.youtube.com/watch?v=Y0ZqKpToTic" rel="nofollow noreferrer">https://www.youtube.com/watch?v=Y0ZqKpToTic</a> 
  except that negative values are allowed.</p>
  
  <p>I have the code below that only works for positive number. Any ideas to make it work for mixed positive and negative values?</p>
  
  <pre><code>class Solution {
  public:
      int Robotmotion(vector&lt;int&gt; &amp;moves, int &amp;d) {
          if (d == 0) return 0;
          if (d &lt; 0) {
              d = -d;
              for (auto &amp;move : moves) move *= -1;
          }
  
          sort(moves.begin(), moves.end());
  
          vector&lt;int&gt; dp(d + 1, d + 1);
  
          dp[0] = 0;
  
          for (int i = 1; i &lt;= d; i++) {
              for (int j = 0; j &lt; moves.size(); j++) {
                  if (moves[j] &lt;= i) {
                      dp[i] = min(dp[i], dp[i - moves[j]] + 1);
                  }
              }
          }
  
          return dp[d] == d + 1 ? -1 : dp[d];
      }
  };
  
  
  
  int main() {
  
      Solution s;
      vector&lt;int&gt; moves = {1,2,3};
      int d = 15;
      int min_steps = s.Robotmotion(moves, d);
      cout &lt;&lt; "Mim steps:" &lt;&lt; endl &lt;&lt; min_steps &lt;&lt; endl;
      return 0;
  }
  </code></pre>