목표 합계

난이도 중급
자주 묻는 질문 아마존 블룸버그 게시물에서 Facebook
깊이 우선 검색 동적 프로그래밍조회수 65

“Target Sum”은 제가 오늘 가지고있는 모든 DPHolics의 특별한 문제입니다. 나머지 사랑스러운 독자들을 버릴 것이라고 걱정할 필요가 없습니다. 우리 모두는 가방을 부수 지 않고 자루에 넣을 수있는 최대 항목 수를 찾으려고 노력하는 고전적인 KnapSack 문제를 겪었습니다.

따라서 더 이상 지체하지 않습니다. 문제에 대해 알아 봅시다. 오늘 나와 함께 사용하는 문제가 있습니다.

문제 정책

주어진 : 정렬 우리가 달성해야 할 요소와 목표 합계로

정황:

  • 우리는 서로 요소를 더하거나 뺄 수 있습니다.
  • 목표를 달성하기 위해 기존 합계와 함께 + 또는 –를 사용할 수 있습니다.

출력은 어떻게되어야합니까?

목표에 도달 할 수있는 방법의 수

예제 배열 : [1,1,1,1,1]

Target_sum : 3

접근 방식 -1

목표 합계를 찾기위한 일반 Jane 재귀

이 접근 방식에는 가능한 모든 조합을 시도한 다음 target_sum으로 이어지는 조합을 선정하는 것이 포함됩니다.

  • 여기서 재귀 함수는 계산하다
  • 가능한 조합을 추적하기 위해 전역 변수 수를 유지합니다.
  • 우리가 새로운 직책을 가질 때마다. 우리는 다음을 확인합니다.
    • pos <= 배열의 길이
      • 지금까지의 합계가 목표와 같으면
        • 증가 카운트
      • 합계가 목표와 같지 않은 경우
        • 돌아 가기 (세그멘테이션 오류를 원하지 않습니까?)
    • 우리가 다음 위치를 계산할 때마다
      • 합계에 다음 요소를 추가합니다.
        • 따라서 "+"를 사용하여
      • 합계에서 다음 요소를 뺍니다.
  • 따라서 "-"사용

이제 프로세스에 대한 개요를 얻었으므로 코드를 작성하겠습니다.

목표 합계에 대한 Java 코드

class Solution
{
    int count=0;
    public void calculate(int[]nums,int pos,int sum,int S)
    {
        if(pos==nums.length)
        {
        if(sum==S)
            count++;
        return;
        }
        calculate(nums,pos+1,sum+nums[pos],S);
        calculate(nums,pos+1,sum-nums[pos],S);   
    }
    public int findTargetSumWays(int[] nums, int S) 
    {
        calculate(nums,0,0,S);
        return count;
    }
}

목표 합계에 대한 C ++ 코드

class Solution 
{
public:
    int count=0;
public:
    void calculate(vector<int>& nums,int pos,int sum,int S)
    {
        if(pos==nums.size())
        {
        if(sum==S)
            count++;
        return;
        }
        calculate(nums,pos+1,sum+nums[pos],S);
        calculate(nums,pos+1,sum-nums[pos],S);   
    }
public:
    int findTargetSumWays(vector<int>& nums, int S)
    {
       calculate(nums,0,0,S);
       return count;
    }
};

복잡성 분석

시간 복잡도 = O (2 ^ n)

왜? = 재귀 트리의 크기는 (2 ^ n) x (n)입니다.

접근 방식 -2

목표 합계를 찾기위한 동적 프로그래밍

  • 배열 Dp 만들기
  • Dp [i] [j] = I 요소로 합계에 도달하는 방법의 수
  • 배열을 채울 때 두 가지를 확인합니다.
    • 요소 + 이전 요소의 합계 <2 * sum
      • 다음 요소를 추가 할 수있을만큼 안전합니다.
      • 따라서 Dp [i] [j] = Dp [i-1] [j] + Dp [i-1] [j + nums [i-1]]
      • 따라서 우리는 "+"를 포함하는 조합을 얻습니다.
    • 이전 요소의 요소 합계가> = 0 인 경우
      • 다음 요소를 뺄 수있을만큼 안전합니다.
      • 따라서 Dp [i] [j] = Dp [i-1] [j] -Dp [i-1] [j + nums [i-1]] Target_sum 찾기
      • 이제 "-"가 포함 된 조합입니다.
  • dp [sum + Target] 반환
    • 이유는 무엇입니까?
    • 범위는 -sum에서 + sum까지 다양합니다.

해당 사례에 대한 다이어그램으로 프로세스 설명

예제 배열의 목표 합계 찾기
주황색, 빨간색 및 녹색으로 강조 표시된 값이있는 주어진 문제에 대한 DP 배열

이미지 키

  • Green-0 값
  • 주황색 -XNUMX이 아닌 값
  • 빨간 대답

코딩 부분을 살펴 보겠습니다.

목표 합계에 대한 Java 코드

class Solution 
{
    public int findTargetSumWays(int[] nums, int S) 
    {
    int sum=0;
    for(int i=0;i<nums.length;i++)
        sum=sum+nums[i];
    if (S<-sum || S>sum) 
        return 0;
    int dp[][]=new int[nums.length+1][sum*2+1];
    dp[0][sum]=1;
    for(int i=1;i<=nums.length;i++)
    {
        for(int j=0;j<sum*2+1;j++)
        {
            if(j+nums[i-1]<sum*2+1)
                dp[i][j]=dp[i][j]+dp[i-1][j+nums[i-1]];
            if(j-nums[i-1]>=0)
                dp[i][j]=dp[i][j]+dp[i-1][j-nums[i-1]];
        }
    }
    return dp[nums.length][sum+S];
    }
}

목표 합계에 대한 C ++ 코드

class Solution 
{
public:
    int findTargetSumWays(vector<int>& nums, int S) 
    {
    int sum=0;
    for(int i=0;i<nums.size();i++)
        sum=sum+nums[i];
    if (S<-sum || S>sum) 
        return 0;
    vector<vector<int>> dp(nums.size() + 1, vector<int>(sum*2 + 1, 0));
    //int dp[nums.size()+1][sum*2+1];
    dp[0][sum]=1;
    for(int i=1;i<=nums.size();i++)
    {
        for(int j=0;j<sum*2+1;j++)
        {
            if(j+nums[i-1]<sum*2+1)
                dp[i][j]=dp[i][j]+dp[i-1][j+nums[i-1]];
            if(j-nums[i-1]>=0)
                dp[i][j]=dp[i][j]+dp[i-1][j-nums[i-1]];
        }
    }
    return dp[nums.size()][sum+S];    
    }
};

복잡성 분석

시간 복잡도 = O (n * sum)

공간 복잡성 = O (n ^ 2)

참조

Translate »