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

WBOY
WBOYオリジナル
2024-08-20 07:04:051121ブラウズ

. eys Keyboard

650。 2 キーキーボード

難易度:

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

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

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

整数 n を指定すると、画面上で文字 'A' を正確に n 回取得するための最小操作数を返します

例 1:

  • 入力: n = 3
  • 出力: 3
  • 説明: 最初に、1 つの文字「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. 問題の理解:

    • 画面上の 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 キーキーボード

<?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 で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

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

  • LinkedIn
  • GitHub

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

声明:
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。