algorithm - 如果在一分钟内移动到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。
关键是除以 2 只允许对 T 的偶数值。 .此外，如果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 以加快速度:if 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);
}