![. eys Keyboard](https://img.php.cn/upload/article/000/000/000/172410864672437.jpg)
650。 2キーキーボード
難易度:中
トピック:数学、動的計画法
メモ帳の画面には「A」という文字が 1 つだけあります。このメモ帳では、ステップごとに 2 つの操作のいずれかを実行できます:
- すべてコピー: 画面上にあるすべての文字をコピーできます (部分的なコピーは許可されません)。
ペースト: 前回コピーした文字をペーストできます。
整数 n を指定すると、
画面上でちょうど n 回文字「A」を取得するための最小操作数を返します.
例1:
- 入力:n = 3
- 出力:3
- 説明:最初は、「A」という 1 つの文字があります。
ステップ 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キーキーボード
リーリー
説明:
- 初期化:dp は、最初は到達不可能な状態を表すために大きな数値 (PHP_INT_MAX) で初期化されます。
- 約数チェック:各数値 i について、すべての約数 d をチェックします。 d に到達するために必要な演算を考慮して dp[i] を更新し、乗算して i を取得します。
- 出力:結果は dp[n] の値であり、画面上に正確に n 文字を取得するために必要な最小限の操作が与えられます。
このアプローチにより、指定された制約に対して最小限の操作を効率的に計算できます。
連絡先リンク
このシリーズが役立つと思われた場合は、GitHub で
リポジトリにスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとってとても意味のあるものになります!
このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:
以上が。キーボードのキーボードの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。