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 キーキーボード

説明：

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

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

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

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

• リンクトイン
• GitHub