650。 2鍵鍵盤

難度： 中

主題： 數學、動態規劃

記事本的螢幕上只有一個字元「A」。您可以在此記事本上為每個步驟執行以下兩個操作之一：

• 全部複製：您可以複製螢幕上出現的所有字元（不允許部分複製）。
• 貼上：可以貼上上次複製的字元。

給定一個整數n，返回在螢幕上準確地出現n次字元「A」的最少操作次數。

範例1：

• 輸入： n = 3
• 輸出： 3
• 解釋： 最初，我們有一個字元「A」。
  • 在步驟1中，我們使用全部複製操作。
  • 在步驟2中，我們使用貼上操作得到'AA'。
  • 在第3步中，我們使用貼上作業來取得'AAA'。

範例2：

• 輸入： n = 1
• 輸出： 0

範例3：

• 輸入： n = 10
• 輸出： 7

範例2：

• 輸入： n = 24
• 輸出： 9

約束：

• 1

暗示：

1. 如果n = 3，最後一步剪貼簿中可能有多少個字元？ n = 7？ n = 10？ n = 24？

解決方案：

我們需要找到最少的操作次數才能在螢幕上精確地顯示 n 個字元「A」。我們將使用動態編程方法來實現這一目標。

1. 理解問題：

   • 我們從螢幕上的一個「A」開始。
   • 我們可以「全部複製」（複製目前螢幕內容）或「貼上」（貼上最後複製的內容）。
   • 我們需要確定螢幕上剛好有 n 個字元「A」所需的最少操作。

2. 動態規劃方法：

   • 使用動態程式設計 (DP) 陣列 dp，其中 dp[i] 表示在螢幕上精確取得 i 個字元所需的最少操作數。
   • 初始化 dp[1] = 0，因為需要 0 次操作才能在螢幕上顯示一個「A」。
   • 對於從 2 到 n 的每個字元 i，透過檢查 i 的每個除數來計算最少運算。如果 i 能被 d 整除，則：
     • 達到 i 所需的運算次數是達到 d 的運算加上 d 相乘得到 i 所需的運算次數。

3. 解決步驟：

   • 使用 INF（或一個大數字）初始化 DP 數組，以獲得除 dp[1] 之外的所有值。
   • 對於從 2 到 n 的每個 i，迭代 i 的可能除數，並根據透過複製和貼上達到 i 所需的操作更新 dp[i]。

讓我們用 PHP 實作這個解決方案：650。 2鍵鍵盤

解釋：

• 初始化： dp 被初始化為一個很大的數字（PHP_INT_MAX），以表示最初不可達的狀態。
• 除數檢查： 對於每個數字 i，檢查所有除數 d。考慮到達 d 所需的操作然後相乘得到 i 來更新 dp[i]。
• 輸出： 結果是 dp[n] 的值，它給出了在螢幕上精確取得 n 個字元所需的最少操作。

這種方法確保我們針對給定的限制有效地計算最少的操作。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給存儲庫 一顆星，或者在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub