單人遊戲最小步數：數軸上步長 a、b、a+b 到達目標

問題描述

數軸上從 A 走到 B，每步可向左/右移動 a、b 或 c=a+b。求最小步數，不可達輸出 -1。多測試用例，T ≤ 1000。

解題思路

此為數論 + BFS/DP 結合問題。關鍵觀察：

• 步長集合 {a, b, a+b} 的最大公約數 g = gcd(a,b)。若 |A-B| 不能被 g 整除，則不可達（-1）。
• 可達時，問題轉化為用最少硬幣找零（硬幣面值 a, b, a+b），可用 BFS 或擴展歐幾里得求解。

詳細解析：博客鏈接