コストに応じた最大ポイント数

1937年。コストに応じた最大ポイント数

難易度: 中

トピック: 配列、動的プログラミング

m x n の整数行列ポイント (0 インデックス付き) が与えられます。 0 点から開始して、行列から取得できる点の数を最大化したいとします。

ポイントを獲得するには、各行で 1 つのセルを選択する必要があります。座標 (r, c) のセルを選択すると、スコアに [r][c] ポイントが追加されます。

ただし、前の行で選択したセルから離れすぎるセルを選択すると、ポイントが失われます。隣接する 2 つの行 r および r + 1 (0 1) および (r + 1, c_{) にあるセルを選択します。 2}) はスコアから abs(c1 - c₂) を _減算します。

達成できる最大ポイント数を返します

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}

ヒント:

動的プログラミングを使ってみましょう。
dp[i][j] は、points[i][j] が選択した最新のセルである場合に取得できるポイントの最大数です。

解決策:

left[j] は、左からの遷移のみを考慮した j 番目の列で達成できる最大値を格納します。
right[j] は、右からの遷移のみを考慮して、j 番目の列に対して達成できる最大値を格納します。

left[j] または right[j] のいずれかに加えて Points[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 で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上がコストに応じた最大ポイント数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。