650。 2 キーキーボード
難易度: 中
トピック: 数学、動的計画法
メモ帳の画面には「A」という文字が 1 つだけあります。このメモ帳では、ステップごとに 2 つの操作のいずれかを実行できます:
- すべてコピー: 画面上にあるすべての文字をコピーできます (部分的なコピーは許可されません)。
- 貼り付け: 前回コピーした文字を貼り付けます。
整数 n を指定すると、画面上で文字 'A' を正確に n 回取得するための最小操作数を返します。
例 1:
-
入力: n = 3
-
出力: 3
-
説明: 最初に、1 つの文字「A」があります。
- ステップ 1 では、すべてコピー操作を使用します。
- ステップ 2 では、貼り付け操作を使用して「AA」を取得します。
- ステップ 3 では、貼り付け操作を使用して「AAA」を取得します。
例 2:
例 3:
例 2:
制約:
ヒント:
- n = 3 の場合、最後のステップでクリップボードには何文字が存在する可能性がありますか? n = 7? n = 10? n = 24?
解決策:
画面上にちょうど n 個の文字「A」を取得するための最小操作数を見つける必要があります。これを実現するために動的プログラミングのアプローチを使用します。
-
問題の理解:
- 画面上の 1 つの「A」から始めます。
- 「すべてコピー」(現在の画面コンテンツをコピー) または「貼り付け」(最後にコピーしたコンテンツを貼り付け) を行うことができます。
- 画面上に正確に n 個の文字「A」を表示するために必要な最小限の操作を決定する必要があります。
-
動的プログラミングのアプローチ:
- 動的プログラミング (DP) 配列 dp を使用します。ここで、dp[i] は、画面上に正確に i 文字を取得するために必要な操作の最小数を表します。
- 画面上に 1 つの「A」を表示するには 0 回の操作が必要なため、dp[1] = 0 を初期化します。
- 2 から n までの各文字数 i について、i のすべての約数をチェックして最小演算を計算します。 i が d で割り切れる場合、次のようになります。
- i に到達するのに必要な演算数は、d に到達する演算と、i を得るために d を乗算するのに必要な演算の合計です。
-
解決手順:
- dp[1] を除くすべての値に対して INF (または大きな数値) を使用して DP 配列を初期化します。
- 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 で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!
このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:
以上が。キーボードのキーボードの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。