机器人运动-动态规划

Question

给定一个无限长度 (x) 的一维世界， 以及可用的移动 (y)，例如 [1, 2, 3, -1, -2, -3]， 和目的地 (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;
}

Answer 1

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