机器人运动 - 动态规划

给定一个无限长（x）的012世界，和可用的移动（y），例如[1,2,3，-1，-2，-3]，和a目的地（d）（即15），编写一个函数，返回到达d所需的最小移动次数（结果）。机器人运动 - 动态规划

例如，如果d = 15，结果= 5 ，因为最优的移动是3，并且它可以完成5次。

此问题与此非常相似：https://www.youtube.com/watch?v=Y0ZqKpToTic 除了允许使用负值之外。

我有下面的代码只适用于正数。任何想法，使其正面和负面的价值混合工作？

class Solution { 
public: 
    int Robotmotion(vector<int> &moves, int &d) { 
     if (d == 0) return 0; 
     if (d < 0) { 
      d = -d; 
      for (auto &move : moves) move *= -1; 
     } 

     sort(moves.begin(), moves.end()); 

     vector<int> dp(d + 1, d + 1); 

     dp[0] = 0; 

     for (int i = 1; i <= d; i++) { 
      for (int j = 0; j < moves.size(); j++) { 
       if (moves[j] <= i) { 
        dp[i] = min(dp[i], dp[i - moves[j]] + 1); 
       } 
      } 
     } 

     return dp[d] == d + 1 ? -1 : dp[d]; 
    } 
}; 



int main() { 

    Solution s; 
    vector<int> moves = {1,2,3}; 
    int d = 15; 
    int min_steps = s.Robotmotion(moves, d); 
    cout << "Mim steps:" << endl << min_steps << endl; 
    return 0; 
}

来源

2017-06-18 Alex

也许我错过了一些东西，或许你的问题并没有复杂化，但为什么不是'steps = abs（distance）/ 3 + abs（distance）％3 == 0？ 0：1;' – user4581301

嗨，在这个问题上，这只是一个简单的例子。移动和目标可以是任何整数。你先不知道动作和动作。 – Alex

超调和回溯是否合法？如果你可以移动10，然后-1，而不是必须得到3三次？ – user4581301

我不认为动态规划可以解决这个问题。相反，您应该将数字视为图中的顶点，并使用BFS解决问题。您甚至可以使用双向BFS来加速此过程。

来源

2017-06-19 10:09:39

机器人运动 - 动态规划

回答

相关问题