。目標金額

494。目標金額

難易度: 中

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

整数配列 nums と整数ターゲットが与えられます。

nums の各整数の前に記号 ' ' と '-' のいずれかを追加して、nums から 式 を構築し、すべての整数を連結したいとします。

• たとえば、nums = [2, 1] の場合、2 の前に「 」、1 の前に「-」を追加して、それらを連結して式「 2-1」を構築できます。

ターゲットとして評価される、構築できるさまざまな 式 の数を返します。

例 1:

• 入力: 数値 = [1,1,1,1,1]、ターゲット = 3
• 出力: 5
• 説明: 数値の合計がターゲット 3 になるようにシンボルを割り当てる方法は 5 つあります。
  • -1 1 1 1 1 = 3
  • 1 - 1 1 1 1 = 3
  • 1 1 - 1 1 1 = 3
  • 1 1 1 - 1 1 = 3
  • 1 1 1 1 - 1 = 3

例 2:

• 入力: 数値 = [1]、ターゲット = 1
• 出力: 1

制約:

• 1
• 0
• 0
• -1000

解決策:

「ターゲット合計」問題では、配列 nums 内の数値を使用して式を作成し、各数値にまたは - 記号を割り当てます。目標は、指定されたターゲットに対して評価されるそのような式の数を計算することです。この問題は、動的プログラミングまたはバックトラッキングを使用して効率的に解決できます。

重要なポイント

1. 入力制約:
   • 配列の長さ: 1
   • 要素の値: 0
   • ターゲット範囲: -1000

2. 出力:

   • ターゲットに評価される式の数を返します。

3. 課題:

   • ソリューションは、ターゲットの小さい値と大きい値の両方を処理する必要があります。
   • バックトラッキングを使用する場合、最大 2²⁰ の組み合わせを効率的に処理します。

アプローチ

この問題は、動的プログラミング (サブセット合計変換) または バックトラッキング を使用して解決できます。以下では、効率化のために 動的プログラミング (DP) を使用します。

主な所見:

1. 数値を P (正の部分集合) と N (負の部分集合) の 2 つのグループに分割すると、次のようになります: target = sum(P) - sum(N)

項を並べ替えます: sum(P) sum(N) = sum(nums)

S を正の部分集合の合計とします。次に、S_{を実行します。} = (合計(数値) ターゲット) / 2

1. (sum(nums) target) % 2 ≠ 0 の場合、合計を分割することは不可能であるため、0 を返します。

計画

1. 数値の合計を計算します。
2. S の式を使用して、目標が達成可能かどうかを確認します。無効な場合は 0 を返します。
3. DP アプローチを使用して、合計が S に等しいサブセットの数を num 単位で求めます 。

このソリューションを PHP で実装してみましょう: 494。目標金額

<?php
/**
 * @param Integer[] $nums
 * @param Integer $target
 * @return Integer
 */
function findTargetSumWays($nums, $target) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$nums = [1, 1, 1, 1, 1];
$target = 3;
echo findTargetSumWays($nums, $target); // Output: 5
?>

説明：

1. 入力検証:

   • S = (sum(nums) target) / 2 を計算します。
   • S が整数でない場合、nums を 2 つのサブセットに分割することは不可能です。

2. 動的プログラミング ロジック:

   • dp[j] は、指定された数値を使用して合計 j を形成する方法の数を表します。
   • dp[0] = 1 から始めて、nums の数値ごとに、j - num を形成するウェイの数を追加して dp[j] を更新します。

3. 結果:

   • すべての数値を処理した後、dp[S] には目標合計を達成する方法の数が含まれます。

チュートリアルの例

入力: 数値 = [1, 1, 1, 1, 1]、ターゲット = 3

1. totalSum = 5、S = (5 3) / 2 = 4.
2. DP 配列を初期化します: dp = [1, 0, 0, 0, 0].
3. 各数値を処理します:
   • 1 の場合: dp を更新: [1, 1, 0, 0, 0].
   • 1 の場合: dp を更新: [1, 2, 1, 0, 0]。
   • 1 の場合: dp を更新: [1, 3, 3, 1, 0].
   • 1 の場合: dp を更新: [1, 4, 6, 4, 1]。
   • 1 の場合: dp を更新: [1, 5, 10, 10, 5]。
4. 結果: dp[4] = 5.

時間計算量

• 時間: O(n x S)、n は nums の長さ、S はターゲットの合計です。
• スペース: DP 配列の場合は O(S)。

出力例

入力: 数値 = [1,1,1,1,1]、ターゲット = 3

出力: 5

このアプローチは、動的計画法を使用して目標合計を形成する方法の数を効率的に計算します。問題をサブセット合計に削減することで、DP の構造を活用してパフォーマンスを向上させます。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上が。目標金額の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。