グリッド内の最大移動数

2684。グリッド内の最大移動数

難易度: 中

トピック: 配列、動的計画法、行列

正の整数で構成される0インデックス m x n行列グリッドが与えられます。

行列の最初の列の任意のセルから開始し、次の方法でグリッドを移動できます。

• セル (行、列) から、(行 - 1、列 1)、(行、列 1)、および (行 1、列 1) のいずれかのセルに移動できます。移動先のセルは、現在のセルの値より厳密に大きくする必要があります。

実行できる動きの最大数を返します。

例 1:

• 入力: グリッド = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15] ]
• 出力: 3
• 説明: セル (0, 0) から開始して、次の動きを行うことができます。
  • (0, 0) -> (0, 1).
  • (0, 1) -> (1, 2).
  • (1, 2) -> (2、3)。 それが実行可能な最大の移動数であることがわかります。

例 2:

• 入力: グリッド = [[3,2,4],[2,1,9],[1,1,7]]
• 出力: 0
• 説明: 最初の列のどのセルからでも移動を実行できません。

制約:

• m == グリッドの長さ
• n == グリッド[i].length
• 2
• 4 5
• 1 6

ヒント:

1. 動的プログラミングを使用して、各セルから実行できる最大移動数を見つけることを検討してください。
2. 最終的な答えは、最初の列のセルの最大値になります。

解決策:

動的プログラミング (DP) を使用して、最初の列の任意のセルから開始して、各セルの最大手数を追跡できます。段階的なアプローチは次のとおりです:

アプローチ：

1. DP 配列の定義: dp[row][col] を、grid[row][col] から開始して可能な移動の最大数を表します。これをすべてのセルに対して 0 で初期化します。

2. グリッドをトラバースします:

   • 最後の列から開始して最初の列に戻ります。列colの各セルについて、col-1の可能な手を計算します。
   • 宛先セルの値が 厳密に大きい。

3. 最大移動量の計算:

   dp テーブルに入力すると、結果は dp の最初の列の最大値になります。これは、最初の列の任意のセルから始まる最大移動を表すためです。

4. エッジケース:

   移動が不可能なケースを処理します (例: すべてのパスが隣接するセルのより低い値または等しい値によってブロックされている場合)。

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

2684。グリッド内の最大移動数

<?php /**
 * @param Integer[][] $grid
 * @return Integer
 */
function maxMoves($grid) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$grid1 = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]];
$grid2 = [[3,2,4],[2,1,9],[1,1,7]];

echo maxMoves($grid1); // Output: 3
echo "\n";
echo maxMoves($grid2); // Output: 0
?>

説明：

1. dp 初期化: 各セルからの最大移動を保存する 2D 配列 dp を作成します。
2. 列のループ: 最後から 2 番目の列から最初の列までを繰り返し、次の列の隣接セルへの移動の可能性に基づいて dp[row][col] を更新します。
3. 最大移動数の計算: 最後に、dp の最初の列の最大値が結果となります。

複雑さの分析:

• 時間計算量: 各セルを 1 回処理するため、O(m x n)。
空間複雑度
• : dp 配列の O(m x n)。
このソリューションは制約を考慮すると効率的であり、指定された制限内で機能します。

連絡先リンク

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

リポジトリ

にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます! このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

LinkedIn
GitHub

以上がグリッド内の最大移動数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。