. 목표합계-PHP 튜토리얼-php.cn

. 목표합계

Susan Sarandon

풀어 주다： 2025-01-02 17:38:43

원래의

369명이 탐색했습니다.

. Target Sum

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 <= nums.length <= 20
0 <= 숫자[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= 대상

해결책:

"Target Sum" 문제는 각 숫자에 또는 - 기호를 할당하여 숫자 배열의 숫자를 사용하여 표현식을 만드는 것과 관련됩니다. 목표는 해당 표현식이 주어진 대상으로 평가되는 수를 계산하는 것입니다. 이 문제는 동적 프로그래밍이나 역추적을 사용하여 효율적으로 해결할 수 있습니다.

핵심사항

입력 제약:
- 배열 길이: 1 <= nums.length <= 20
- 요소 값: 0 <= nums[i] <= 1000
- 대상 범위: -1000 <= 대상 <= 1000
출력:
- 타겟으로 평가되는 표현식의 개수를 반환합니다.
도전과제:
- 솔루션은 목표의 작은 값과 큰 값을 모두 처리해야 합니다.
- 역추적 사용 시 최대 2²⁰개의 조합을 효율적으로 처리합니다.

접근방법

이 문제는 동적 프로그래밍(부분합 합 변환) 또는 역추적을 사용하여 해결할 수 있습니다. 아래에서는 효율성을 위해 동적 프로그래밍(DP)을 사용합니다.

주요 관찰:

nums를 P(양성 하위 집합)와 N(음성 하위 집합)의 두 그룹으로 나누면 다음과 같습니다. target = sum(P) - sum(N)

항 재배열: sum(P) sum(N) = sum(nums)

S를 양의 부분 집합의 합으로 둡니다. 그런 다음: S = (합계(숫자) 목표) / 2

(sum(nums) target) % 2 ≠ 0인 경우 합계를 분할할 수 없으므로 0을 반환합니다.

계획

숫자의 총합을 계산합니다.
S의 공식을 이용해 목표 달성 가능 여부를 확인하세요. 유효하지 않은 경우 0을 반환합니다.
DP 접근 방식을 사용하여 합계가 S와 같은 숫자의 하위 집합 수를 찾습니다.

이 솔루션을 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
?>

로그인 후 복사

설명:

입력 유효성 검사:
- S를 계산합니다 = (sum(nums) target) / 2.
- S가 정수가 아닌 경우 숫자를 두 개의 하위 집합으로 분할하는 것은 불가능합니다.
동적 프로그래밍 논리:
- dp[j]는 주어진 숫자를 사용하여 합 j를 형성하는 방법의 수를 나타냅니다.
- dp[0] = 1부터 시작하여 nums의 각 숫자에 대해 j - num을 형성하는 방법의 수를 더하여 dp[j]를 업데이트합니다.
결과:
- 모든 숫자를 처리한 후 dp[S]에는 목표 합계를 달성하는 방법의 개수가 포함됩니다.

예시 연습

입력: nums = [1, 1, 1, 1, 1], 대상 = 3

totalSum = 5, S = (5 3) / 2 = 4.
DP 배열 초기화: dp = [1, 0, 0, 0, 0].
각 번호 처리:
- 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].
결과: dp[4] = 5.