。キーボードのキーボード

650。 2キーキーボード

難易度:中

トピック:数学、動的計画法

メモ帳の画面には「A」という文字が 1 つだけあります。このメモ帳では、ステップごとに 2 つの操作のいずれかを実行できます:

• すべてコピー: 画面上にあるすべての文字をコピーできます (部分的なコピーは許可されません)。
ペースト: 前回コピーした文字をペーストできます。

整数 n を指定すると、

画面上でちょうど n 回文字「A」を取得するための最小操作数を返します.

例1:

• 入力:n = 3
• 出力:3
• 説明:最初は、「A」という 1 つの文字があります。
  ステップ 1 では、すべてコピー操作を使用します。
  ステップ 2 では、貼り付け操作を使用して「AA」を取得します。
  ステップ 3 では、貼り付け操作を使用して「AAA」を取得します。

例 2:

• 入力:n = 1
• 出力:0

例 3:

• 入力:n = 10
• 出力:7

例 2:

• 入力:n = 24
• 出力:9

制約:

1

ヒント:

n = 3 の場合、最後のステップでクリップボードには何文字が存在する可能性がありますか? n = 7? n = 10? n = 24?

解決策:

画面上にちょうど n 個の文字「A」を取得するための最小操作数を見つける必要があります。これを達成するために動的プログラミングのアプローチを使用します。

1. 問題の理解:

   画面上の 1 つの「A」から始めます。
   「すべてコピー」(現在の画面コンテンツをコピー) または「貼り付け」(最後にコピーしたコンテンツを貼り付け) を実行できます。
   画面上に正確に n 個の文字「A」を表示するために必要な最小限の操作を決定する必要があります。

2. 動的プログラミングのアプローチ:

   動的プログラミング (DP) 配列 dp を使用します。ここで、dp[i] は、画面上に正確に i 文字を取得するために必要な操作の最小数を表します。
   画面上に 1 つの「A」を表示するには 0 回の操作が必要なため、dp[1] = 0 を初期化します。
   2 から n までの各文字数 i について、i のすべての約数をチェックして最小演算を計算します。 i が d で割り切れる場合、次のようになります。
   • i に到達するために必要な演算の数は、d に到達するための演算と、i を得るために d を乗算するために必要な演算の合計です。

3. 解決手順:

   dp[1] を除くすべての値に対して INF (または大きな数値) を使用して DP 配列を初期化します。
   2 から n までの各 i について、i の可能な約数を反復処理し、コピー アンド ペーストによって i に到達するために必要な操作に基づいて dp[i] を更新します。

このソリューションを PHP で実装してみましょう:

650。 2キーキーボード
リーリー

説明：

• 初期化:dp は、最初は到達不可能な状態を表すために大きな数値 (PHP_INT_MAX) で初期化されます。
• 約数チェック:各数値 i について、すべての約数 d をチェックします。 d に到達するために必要な演算を考慮して dp[i] を更新し、乗算して i を取得します。
• 出力:結果は dp[n] の値であり、画面上に正確に n 文字を取得するために必要な最小限の操作が与えられます。

このアプローチにより、指定された制約に対して最小限の操作を効率的に計算できます。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で

リポジトリにスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとってとても意味のあるものになります！

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• リンクトイン
• GitHub

以上が。キーボードのキーボードの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。