algorithm - 最短路径问题的变体

Question

谁能帮我解决这个问题——我能想到的就是递归调用一个函数(但这似乎并不奏效)。

假设我从零开始，并在每一步添加两个数字中的一个。所以，一开始我可能会将 n1 或 n2 加到零；所以新的没有。变为 n1 或 n2，然后添加 n1 或 n2。

这样做，我怎样才能知道是否达到了某个数字，比如 N？如果达到这个数字，我怎样才能找到它到达 N 的最短路径(解决方案可能是 n1,n1,n2 之类的东西)？

Answer 1

这看起来更像是 linear Diophantine equation与最短路径问题相比具有非负性约束。

从文章中总结:如果d是n₁和n₂的最大公约数，那么当且仅当N是倍数时才有解d。如果是，则有无穷多个解决方案(包括最小的一个)，可以通过 extended Euclidean algorithm 找到。 .您只需要做一点(哈!)额外的工作来确定是否存在非负整数的最小解。 (例如，2n₁ + 3n₂ = 1 没有非负解。)