グリッド内の最大移動数-PHPチュートリアル-php.cn

グリッド内の最大移動数

Linda Hamilton

リリース： 2024-10-30 13:27:03

オリジナル

276 人が閲覧しました

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

難易度: 中

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

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

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

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

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

例 1:

Maximum Number of Moves in a Grid

入力: グリッド = [[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:

Maximum Number of Moves in a Grid

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

制約:

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

ヒント:

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

解決策:

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

アプローチ：

DP 配列の定義: dp[row][col] を、grid[row][col] から開始して可能な移動の最大数を表します。これをすべてのセルに対して 0 で初期化します。
グリッドをトラバースします:
- 最後の列から開始して最初の列に戻ります。列colの各セルについて、col-1の可能な手を計算します。
- 宛先セルの値が厳密に大きい。
最大移動量の計算:
エッジケース:

このソリューションを 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
?>

ログイン後にコピー

説明：