主題
題目連結：
題目意譯：
你被給定一個索引值從 0 開始數且由正整數組成的陣列 nums。你可以對該陣列做以下操作任意次：
選定一個索引值 i 使得 0 ≦ i < n - 1 並將 nums[i] 或是 nums[i + 1] 替換成兩者的 gcd 值。
回傳讓 nums 中所有元素值變為 1 最少所需的操作數。如果這不可能做到，則回傳 -1。
兩整數的 gcd 為兩者的最大公因數（Greatest Common Divisor）。
限制：
2 ≦ nums.length ≦ 50
1 ≦ nums[i] ≦ 10 ^ 6
範例測資：
範例 1：
輸入： nums = [2,6,3,4]
輸出： 4
解釋： 我們可以執行以下操作：
- 選定索引值 i = 2 並將 nums[2] 之值替換成 gcd(3, 4) = 1。現在 nums 變為 [2,6,1,4]。
- 選定索引值 i = 1 並將 nums[1] 之值替換成 gcd(6, 1) = 1。現在 nums 變為 [2,1,1,4]。
- 選定索引值 i = 0 並將 nums[0] 之值替換成 gcd(2, 1) = 1。現在 nums 變為 [1,1,1,4]。
- 選定索引值 i = 2 並將 nums[3] 之值替換成 gcd(1, 4) = 1。現在 nums 變為 [1,1,1,1]。
範例 2：
輸入： nums = [2,10,6,14]
輸出： -1
解釋： 可以證明此例中不可能將所有元素值變為 1。
解題思維：
首先，如果 nums 中所有數字的最大公因數不為 1，則不可能將 nums 中所有數值都變成 1。
接著，如果 nums 裡面有 1 存在且數量為 c 個，則所求操作數即為 nums.length - c。
經過以上兩次判斷之後，代表著我們需要從 nums 中先創造出數字 1 接著就可以用第二個結論來快速算出答案。
那要怎麼創造出數字 1 呢？可以看到我們一次會把某個 nums[i] 或是 nums[i + 1] 換成 nums[i] 和 nums[i + 1] 的最大公因數。因此以 nums[i] 的觀點來看，這個最大公因數的資訊可以逐漸地往 nums[i - 1] 、 nums[i - 2] 、……的方向以及 nums[i + 2] 、 nums[i + 3] 、……的方向傳遞來得到更小的最大公因數值。
因此得到 1 的時候，可以往回推到「起點」，而「起點」到 1 出現地將會形成一個子陣列。而子陣列的長度 - 1 即為創造 1 所需的操作數。
所以我們可以窮舉出所有可能的子陣列來判斷在那些可以創造出 1 的子陣列中，哪些長度最短。
而假設長度最短為 L。則結合上面的結論可以得到所求操作數即為 nums.length - L - 2。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
