如果一分钟内可以移动到N+1、N-1、2*N，如何在最短时间内到达目标楼层？

Question

这是我在面试中被要求解决的问题，但是我在面试中实现的代码无法通过所有测试用例，问题正如标题所说，给定N和T（T >= N），分别是初始楼层和目标楼层，一分钟可以移动到当前楼层+1、当前楼层-1或2*当前楼层，到达目标最少需要多少时间？我认为这是一个典型的DP问题，我在面试时就是这样

@lru_cache(None)
def solve(cur):
    if cur >= target: return cur - target
    if cur * 2 >= target:
        # if current floor * 2 < target, we can move to current floor + 1 each time or move backward to (target + 1) // 2 and move current floor * 2 next time, and if target is odd, we need extra 1 move
        return min(target - cur, cur - (target + 1) // 2 + 1 + (target % 2))
    return min(solve(cur + 1), solve(cur * 2)) + 1

我测试了一些案例，似乎可以，我不明白为什么它在面试时不能通过所有测试案例，

更新---------------------------------------- ------------------

我尝试使用 Dijkstra 来解决这个问题，但代码变得有点乱，我想如果问题要求找到最短距离，也许我们可以使用 BFS，我认为这是正确的解决方案，所以下面是代码

def solve():
    while(True):
        N, T = map(int, input().split())
        q = deque([N])
        vis = [False] * (T * 2)
        vis[N] = True
        steps = 0
        while q:
            for _ in range(len(q)):
                u = q.popleft()
                if u == T:
                    print(f'reach target in {steps} minutes')
                    break
                cand = [u - 1, u + 1, u * 2] if u < T else [u - 1]
                for v in cand:
                    if v > 0 and not vis[v]:
                        vis[v] = True
                        q.append(v)
            steps += 1

Answer 1

一个简单的方法是从目标 T 开始，找出我们需要多少次迭代才能下降到初始值 N。这里，允许的操作是 +1、-1 和除以 2。

关键是只有T的偶数才允许除以2。此外，如果 T 甚至有效，那么除以 2 似乎很清楚，除非 T 足够接近 N。通过比较 1 + nsteps(N, T/2) 和 T - N.

解决了这个小问题

如果T是奇数，我们必须比较nsteps(N, T-1)和nsteps(N, T+1)。

最后但同样重要的是，如果T小于N，则步数等于N - T。

复杂度：??

这里有一个简单的 C++ 实现来说明算法。它应该很容易适应任何语言。

#include <iostream>
#include <algorithm>

int nsteps (int n, int t) {
    if (t <= n) {
        return n - t;
    }
    if (t%2 == 0) {
        return std::min (1 + nsteps(n, t/2), t-n);
    }
    return 1 + std::min (nsteps(n, t-1), nsteps(n, t+1));
}
    
int main () {
    int n, t;
    std::cin >> n >> t;
    std::cout << nsteps (n, t) << std::endl;
    return 0;
}

实际上，正如@David Eisenstat 在评论中指出的那样，它仍然很慢，至少在某些情况下是这样。例如，对于输入 1 1431655765，它需要调用 10891541 次函数。我在后面修改了代码，通过使用 T 模 4 的值来加快速度：如果 T 足够大，我们可以在 T 为奇数时在两条道路之间做出决定.同样的测试用例，现在只需要调用46次

在这种情况下，复杂度似乎确实等于 O(log T)。

int cpt2 = 0;
long long int nsteps2 (long long int n, long long int t) {
    cpt2++;
    if (t <= n) {
        return n - t;
    }
    if (t%2 == 0) {
        return std::min (1ll + nsteps2(n, t/2), t-n);
    }
    if (t/4 < n) return 1ll + std::min (nsteps2(n, t-1), nsteps2(n, t+1));
    if (t%4 == 1) return 1ll + nsteps2(n, t-1);
    else return 1ll + nsteps2(n, t+1);
}

Answer 2

正如您所提到的，我们可以使用正常的 BFS 搜索这个问题，因为我们在楼层之间移动的方向已经给出为楼层 + 1 或楼层 - 1 或楼层 / 2。根据我的理解，楼层/ 2 移动只有在我们处于偶数层时才有可能。

这是我的 java 代码：


int findSteps(int n, int t) {
    if (n > t) {
        return n - t;
    }
    if (n == t) {
        return 0;
    }
    Queue<Integer> queue = new LinkedList<>();
    Set<Integer> visited = new HashSet<>();
    queue.offer(n);
    visited.add(n);
    int steps = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i=0; i<size; i++) {
            int currentFloor = queue.poll();
            if (currentFloor == t)
                return steps;
            int possibleMove1 = currentFloor + 1;
            int possibleMove2 = currentFloor - 1;
            int possibleMove3 = currentFloor % 2 == 0 ? currentFloor / 2 : -1;
           // out of bound conditions or visited condition 
            if (possibleMove1 < t && possibleMove1 > n && !visited(possibleMove1)) {
                queue.offer(possibleMove1);
                visited.add(possibleMove1);
            }
            if (possibleMove2 < t && possibleMove2 > n && !visited(possibleMove2)) {
                queue.offer(possibleMove2);
                visited.add(possibleMove2);
            }
            if (possibleMove3 < t && possibleMove3 > n && !visited(possibleMove3)) {
                queue.offer(possibleMove1);
                visited.add(possibleMove1);
            }
        }
        steps += 1;
    }
    return -1;
}

注意：有一些重复代码可以移至单独的函数并改用该函数。

如果一分钟内可以移动到N+1、N-1、2*N，如何在最短时间内到达目标楼层？

how to get to the target floor in minimum time if one can move to N + 1, N - 1 and 2 * N in one minute?

algorithm

dynamic-programming