Arithmetic problem | Target Sum

4438 단어 Arithmeticproblemeachas
제목은 다음과 같습니다.
You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.
Find out how many ways to assign symbols to make sum of integers equal to target S. 
Example 1:
Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:

-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

There are 5 ways to assign symbols to make the sum of nums be target 3.

문제 풀이 사고방식: 이 문제는 어느 정도 난이도가 있다...그러나 수열의 수를 모두 사용해야 하기 때문에 정수의 수를 선택하면 나머지 수는 마이너스를 대표한다.먼저 추상적인 문제를 합리적으로 가정하고 S(r)가 수열에서 정수를 충당하는 수의 누적과, S(l)가 남은 수의 누적과를 가정하면 제목에 따라 S(r)-S(l)=target을 쉽게 얻을 수 있다.
그러나 두 가지 미지수는 확실히 알 수 없고, 또 무엇을 보충할 수 있습니까?그게 모든 수의 합을 세어보는 거지...추상은 S(a)로 모든 수의 누적 합을 수열하고 S(r)+S(l)=S(a)를 얻는다는 뜻이다.
두 가지 형식을 더하면 S(r)+S(r)=target+S(a)를 얻을 수 있습니다.그러면 S(r)=(target+S(a))/2.현재의 문제는'수열에서 n개의 누적을 찾아내는 것과 같다(target+S(a)/2'로 완벽하게 변했다.수열 안에 모두 정수가 있기 때문에 (target+S(a))/2도 정수가 되어야 하지만 target+S(a)도 홀수가 아니다.
자, 계속 추상적으로 이 문제를 가정하면 B(n,k)가 전 n개수에서 특정한 수의 누적과 k를 추출하기 위해 규모를 줄이는 상황에서 n개수의 마지막 수 p를 설정하면 반드시 선택한다. 그러면 앞 부분의 데이터는 특정한 수의 누적과 k-p를 추출해야 하기 때문에 B(n,k)=B(n-1,k-p)를 얻는다.
이로써 저규모 데이터는 n규모 데이터로 점차적으로 미루면 된다.
문제 해결 방법 코드:
int Method(int *n,int len,int target)
{
    int *matrix=new int[len+1];
    ZeroMemory(matrix,len*4+4);
    int aspt=accumulate(n,n+len,0)+target;
    if(aspt&1||len<=0) return 0;
    target=aspt/2;
    matrix[0]=1;

    for(int i=0;i<len;++i)
        for(int p=target;p>=n[i];--p)
        {
            matrix[p]+=matrix[p-n[i]];
        }

    int res=matrix[target];
    delete[] matrix;
    return res;
}
POJ 1256 Anagram
300번 만들었어요. 가위바위보 웹 앱.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage