。眼睛鍵盤

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 鍵鍵盤

<?php
// Example usage
echo minOperations(3); // Output: 3
echo minOperations(1); // Output: 0
echo minOperations(10) . "\n"; // Output: 7
echo minOperations(24) . "\n"; // Output: 9
?>

解釋：

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

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

聯絡連結

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

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

• 領英
• GitHub

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