最大點數與成本

1937 年。花費的最大積分

難度：中

主題：數組，動態規劃

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

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

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

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

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]是您可以擁有的最大點數。

解：

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

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

讓我們用 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
?>

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

聯絡連結

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

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

• 領英
• GitHub

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