使两个数字相等的最少运算次数

Question

我接受了采访，但无法想出解决这个问题的明确/最佳解决方案。

给定 2 个数字 A 和 B，我们需要使用最少的以下操作将数字 A 转换为 B：

• 减 1
• 添加 1
• 乘以 2
• 除2
• 乘以 3
• 划分3

例如：如果 a=3 且 b=7，则程序应输出 2。

第一个操作：*2 -> 3*2 = 6。

第二次操作：+1 -> 6 + 1 =7。

例如：如果 a=10 且 b=60，则程序应输出 2。

第一次操作：*2 -> 10*2 = 20。

第二次操作：*3 -> 20*3 = 60

由于我们可以在 2 次运算后将 m (10) 变为 n (60)，所以答案是 2。

尝试使用动态规划和递归方法但无济于事。有小费吗？

Answer 1

将数字视为图的节点，将运算视为边。使用BFS寻找从A到B的最短路径。

我认为你可以将节点限制为 A 和 B 绝对值的 3 倍，以最小化步骤数，但这不是必需的。

空间和时间复杂度与答案成正比，例如，如果答案是2，在最坏的情况下我们必须访问6*2=12个节点。