コストに応じた最大ポイント数
1937年。コストに応じた最大ポイント数
難易度: 中
トピック: 配列、動的プログラミング
m x n の整数行列ポイント (0 インデックス付き) が与えられます。 0 点から開始して、行列から取得できる点の数を最大化したいとします。
ポイントを獲得するには、各行で 1 つのセルを選択する必要があります。座標 (r, c) のセルを選択すると、スコアに [r][c] ポイントが追加されます。
ただし、前の行で選択したセルから離れすぎるセルを選択すると、ポイントが失われます。隣接する 2 つの行 r および r + 1 (0 1) および (r + 1, c) にあるセルを選択します。 2) はスコアから abs(c1 - c2) を 減算します。
達成できる最大ポイント数を返します
。abs(x) は次のように定義されます:
- x の x >= 0.
- -x (x
- 入力: 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 です。
- 入力: ポイント = [[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
例 1:
例 2:
制約:
ヒント:
- 動的プログラミングを使ってみましょう。
- 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 で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!
このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:
- GitHub
以上がコストに応じた最大ポイント数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
ホットAIツール
Undress AI Tool
脱衣画像を無料で
Undresser.AI Undress
リアルなヌード写真を作成する AI 搭載アプリ
AI Clothes Remover
写真から衣服を削除するオンライン AI ツール。
Clothoff.io
AI衣類リムーバー
Video Face Swap
完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。
人気の記事
ホットツール
メモ帳++7.3.1
使いやすく無料のコードエディター
SublimeText3 中国語版
中国語版、とても使いやすい
ゼンドスタジオ 13.0.1
強力な PHP 統合開発環境
ドリームウィーバー CS6
ビジュアル Web 開発ツール
SublimeText3 Mac版
神レベルのコード編集ソフト（SublimeText3）
ホットトピック
1794
16
1740
56
1590
29
1468
72
267
587
2つのPHPアレイを組み合わせる方法ユニークな値は？
Jul 02, 2025 pm 05:18 PM
2つのPHPアレイをマージし、一意の値を保持するには、2つの主要な方法があります。 1.インデックスアレイまたは重複排除のみの場合、array_mergeとarray_uniqueの組み合わせを使用します：最初のマージArray_merge（$ array1、$ array2）を使用してから、array_unique（）を使用して、最終的にすべての一意の値を含む新しいアレイを取得します。 2。関連アレイと最初の配列のキー値のペアを保持したい場合は、演算子を使用してください。$ result = $ array1 $ array2。これらの2つの方法は、キー名が保持されているか焦点があるかに応じて、異なるシナリオに適用できます。
LinuxでPHP開発環境を構成する手順
Jun 30, 2025 am 01:57 AM
tosetupaphpdevelopmentenvironmentonlinux、instalfpandrequiredextensions、setupawebeberverlikeapacheornginx、testwithaphpfile、andoptionallyinstallmysqlandcomposer.1.installphpandextensionsviapackagemanager（
パスワード強度のPHP Regex
Jul 03, 2025 am 10:33 AM
パスワードの強度を判断するには、定期的な処理と論理処理を組み合わせる必要があります。基本的な要件には以下が含まれます。1。長さは8桁以上です。 2。少なくとも小文字、大文字、および数字を含む。 3。特別な文字制限を追加できます。高度な側面に関しては、文字の継続的な重複と漸進的/減少シーケンスを避ける必要があります。これには、PHP機能検出が必要です。同時に、ブラックリストを導入して、パスワードや123456などの一般的な弱いパスワードをフィルタリングする必要があります。最後に、評価の精度を向上させるためにZXCVBNライブラリを組み合わせることをお勧めします。
PHPでのクロスサイトリクエスト偽造（CSRF）攻撃を防ぐにはどうすればよいですか？
Jun 28, 2025 am 02:25 AM
topreventcsrfattacksinphp、demifficanti-csrftokens.1）生成と測定と測定を繰り返し、orbin2hex（random_bytes（32））、savethemin $ _ session、andincludeTheminformsashdidnputs.2）
ファイルアップロードをPHPで安全に処理する方法は？
Jul 08, 2025 am 02:37 AM
PHPファイルのアップロードを安全に処理するには、ソースとタイプを確認し、ファイル名とパスを制御し、サーバー制限を設定し、メディアファイルを2回プロセスする必要があります。 1.トークンを介してCSRFを防ぐためにアップロードソースを確認し、ホワイトリストコントロールを使用してFINFO_FILEを介して実際のMIMEタイプを検出します。 2。ファイルをランダムな文字列に変更し、検出タイプに従って非WEBディレクトリに保存する拡張機能を決定します。 3。PHP構成は、アップロードサイズを制限し、一時的なディレクトリnginx/apacheはアップロードディレクトリへのアクセスを禁止します。 4. GDライブラリは写真を再利用して、潜在的な悪意のあるデータをクリアします。
PHPでコードをコメントします
Jul 18, 2025 am 04:57 AM
PHPコメントコードには3つの一般的な方法があります。1。//＃を使用して1行のコードをブロックすると、//を使用することをお勧めします。 2。使用/.../複数の行でコードブロックをラップするには、ネストすることはできませんが交差することができます。 3. / if（）{}を使用するなどの組み合わせスキルコメントロジックブロックを制御するか、エディターショートカットキーで効率を改善するには、シンボルを閉じることに注意を払い、使用時にネストを避ける必要があります。
PHPコメントを書くためのヒント
Jul 18, 2025 am 04:51 AM
PHPコメントを書くための鍵は、目的と仕様を明確にすることです。コメントは、「何が行われたのか」ではなく「なぜ」を説明する必要があり、冗長性や単純さを避けてください。 1.読みやすさとツールの互換性を向上させるために、クラスおよびメソッドの説明にdocblock（/*/）などの統合形式を使用します。 2。JSジャンプを手動で出力する必要がある理由など、ロジックの背後にある理由を強調します。 3.複雑なコードの前に概要説明を追加し、手順でプロセスを説明し、全体的なアイデアを理解するのに役立ちます。 4. TodoとFixmeを合理的に使用して、To Doアイテムと問題をマークして、その後の追跡とコラボレーションを促進します。優れた注釈は、通信コストを削減し、コードメンテナンスの効率を向上させることができます。
発電機はPHPでどのように機能しますか？
Jul 11, 2025 am 03:12 AM
ageneratorinphpisamemory-efficientwaytoateate-overdeatatasetasetasetasetsinging valueseintimeintimeturningthemallatonce.1.generatorsususedeywordproducevaluesedemand、memoryusage.2を還元すること。2
