網格中的最大移動次數

2684。網格中的最大移動次數

難度：中

主題：陣列、動態規劃、矩陣

給你一個0索引 m x n矩陣網格，由正個整數組成。

您可以從矩陣第一列中的任何單元格開始，並按以下方式遍歷網格：

• 從單元格(row, col) 中，您可以移動到任何單元格：(row - 1, col 1)、(row, col 1) 和(row 1, col 1)，這樣您移動到的單元格應該嚴格大於目前單元格的值。

回傳您可以執行的最大移動次數。

範例1：

• 輸入： 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：

• 輸入： grid = [[3,2,4],[2,1,9],[1,1,7]]
• 輸出： 0
• 解釋：從第一列的任何儲存格開始，我們無法執行任何移動。

約束：

• m == grid.length
• n == grid[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. 循環列：我們從倒數第二列迭代到第一列，根據可能移動到下一列中的相鄰單元格來更新 dp[row][col]。
3. 最大移動計算：最後dp第一列的最大值給出結果。

複雜度分析：

• 時間複雜度：O(m x n)，因為我們處理每個單元一次。
• 空間複雜度：O(m x n) 對於 dp 陣列。

考慮到限制，該解決方案是有效的，並且將在提供的限制內工作。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給

存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是網格中的最大移動次數的詳細內容。更多資訊請關注PHP中文網其他相關文章！