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

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

難易度: 中

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

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

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

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

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

。

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}

ヒント:

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

解決策:

ソリューションをいくつかのステップに分けることができます:

ステップ 1: DP 配列を定義する

2D 配列 dp を使用します。ここで、dp[i][j] は、行 i と列 j のセルを選択することで達成できる最大点を表します。

ステップ 2: DP アレイを初期化する

コストを差し引く前の行がないため、dp の最初の行をポイントの最初の行と同じになるように初期化します。

ステップ 3: 各行の DP 値を計算する

後続の各行について、前の行からの切り替えコストを考慮して、各列の可能な最大ポイントを計算します。

行 i-1 から行 i への遷移を効率的に計算するには、左右の 2 つの補助配列を使用できます。

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

ステップ 4: 各行の DP を更新する

行 i の各列 j について:

left[j] または right[j] のいずれかに加えて Points[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 x n)) であり、制約を考慮すると効率的です。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

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

• LinkedIn
• GitHub

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