。眼睛鍵盤

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

以上是。眼睛鍵盤的詳細內容。更多資訊請關注PHP中文網其他相關文章！