最大點數與成本

1937 年。花費的最大積分

難度：中

主題：數組，動態規劃

給定一個 m x n 整數矩陣點（0 索引）。從 0 點開始，您希望最大化可以從矩陣中獲得的點數。

要獲得積分，您必須在每一行中選擇一個儲存格。選擇座標 (r, c) 的儲存格將將分[r][c]加到您的分數中。

但是，如果您選擇的儲存格距離您在上一行中選擇的儲存格太遠，您將失去分數。對於每兩個相鄰行r 和r + 1（其中0 ），選取座標(r, c1_{) 和(r + 1, c} 處的單元格2) 將從您的分數中減去 _abs(c1 _{- c}2

)。

回傳您可以得到的最大分數

。

abs(x) 定義為：

x 表示 x >= 0。
-x 表示 x

範例1：



• 輸入：
l1 = [2,4,3], l2 = [5,6,4]
• 輸出：
9
• 說明：
  藍色儲存格表示要選取的最佳儲存格，其座標為 (0, 2)、(1, 1) 和 (2, 0)。
  您的分數加上 3 + 5 + 3 = 11。
  但是，您必須從分數中減去abs(2 - 1) + abs(1 - 0) = 2。
  您的最終得分是 11 - 2 = 9。

範例2：



• 輸入：
點 = [[1,5],[2,3],[4,2]]
• 輸出：
11
• 說明：
  藍色儲存格表示要選取的最佳儲存格，其座標為 (0, 1)、(1, 1) 和 (2, 0)。
  您的分數加上 5 + 3 + 4 = 12。
  但是，您必須從分數中減去abs(1 - 1) + abs(1 - 0) = 1。
  您的最終得分是 12 - 1 = 11。

約束：

m == 點.長度
n == 點[r].length
• ^{1 5}
• ^{1 5}
• ^{0 5}

提示：

嘗試使用動態規劃。
如果點[i][j]是您最近選擇的儲存格，則dp[i][j]是您可以擁有的最大點數。

解：

我們可以將解法分解為幾個步驟：

第 1 步：定義 DP 數組

我們將使用二維數組 dp，其中 dp[i][j] 表示選擇第 i 行和 j 列的單元格可以獲得的最大點數。

步驟2：初始化DP陣列

將第一行 dp 初始化為與第一行點相同，因為沒有先前的行來減去成本。

步驟 3：計算每行的 DP 值

對於每個後續行，我們考慮到從前一行切換的成本來計算每列的最大可能點。

為了有效計算從第 i-1 行到第 i 行的轉換，我們可以使用左右兩個輔助數組：

left[j] 將儲存我們可以為第 j 列實現的最大值，僅考慮從左側的轉換。
right[j] 將儲存我們可以為第 j 列實現的最大值，僅考慮從右側的轉換。

步驟 4：更新每行的 DP

對於第 i 行中的每列 j：

使用 left[j] 或 right[j] 中的最大值加上點 [i][j] 來更新 dp[i][j]。

步驟 5：傳回最後一行的最大值

結果將是 dp 陣列最後一行的最大值。

讓我們用 PHP 實作這個解：1937。花費的最大積分

<?php
// Example usage:
$points1 = [[1, 5], [2, 3], [4, 2]];
$points2 = [[2, 4, 3], [5, 6, 4]];
echo maxPoints($points1); // Output: 11
echo maxPoints($points2); // Output: 9
?>

解釋：

• 左數組和右數組：
這些幫助我們透過考慮前一行的值來計算每個單元格可以獲得的最大分數，有效地考慮跨列移動的損失。
• 動態程式設計方法：
此方法可確保每一行都是基於前一行計算的，使解決方案可針對大型矩陣進行擴展。

這種方法的時間複雜度為 (O(m × n))，在給定限制的情況下是有效的。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

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

• 領英
• GitHub

以上是最大點數與成本的詳細內容。更多資訊請關注PHP中文網其他相關文章！