SPOJ COINS DP 및 재귀 적 접근

Question

최근에 DP 문제를 해결하기 시작했고 나는 COINS를 발견했습니다. memoization 함께 DP를 사용하여 그것을 해결하기 위해 노력하고 int 배열을 사용하는 경우 잘 작동합니다. 은 여기 내 접근 방식 (왼쪽 약간 수정)입니다 :

#include <stdio.h> 
#include <stdlib.h> 
int dp[100000]; 
long long max(long x, long y) 
{ 
    if (x > y) 
     return x; 
    else 
     return y; 
} 
int main() 
{ 
    int n,i; 
    scanf("%d",&n); 
    dp[0]=0; 
    for(i=1;i<=n;i++) 
    { 
     dp[i]=max(i,dp[i/2] + dp[i/3] + dp[i/4]); 
    } 
    printf("%d\n",dp[n]); 

    return 0; 
} 

그러나 나는 SIGSEGV를 얻을 오래 오래 배열을 사용 나는 즉시 이해하지 않습니다. 필자는 수색을했으며, 내가 이해하지 못하는 재귀 적 해결책이있는 것으로 보인다. 누군가 나를 도와 줄 수 있습니까?

Answer 1

한계는 n<=10e9이며, 배열 크기는 항상 메모리 오버플로가 발생하므로 SIGSEGV이됩니다. dp-array의 유형이 무엇인지는 중요하지 않습니다.

코드에 다른 오류가 있습니다. 첫째, 테스트 케이스가 있으며, EOF까지 읽어야합니다. 둘째, 한계가 10e9이므로 n 번 반복됩니다! 틀림없이 TLE.

이제 재귀 솔루션, 메모이 제이션을 사용하여 :

을 첫째, 배열에 10e6까지 답변 값을 저장합니다. 시간을 절약하는 데 도움이됩니다. 으로 수행 할 수 있습니다

ans = coins(n); 

는 coins 기능을 구현, 모든 입력 n를 들어, 같은 해결책을 찾아,

long long dp[1000000] = {0}; 
for(int i = 1; i < 1000000; i++){ 
    dp[i] = max(i, dp[i/2] + dp[i/3] + dp[i/4]); 
} 

지금과 같은 :

long long coins(long long n){ 
    if (n < 1000000) 
     return dp[n]; 
    return coins(n/2) + coins(n/3) + coins(n/4); 
} 

왜 재귀 솔루션 작품 :

모두 n >= 12에 대한 대답은 ans[n/2] + ans[n/3] + ans[n/4]이 될 것이므로 n > 10e6의 경우 그 답이 반환된다는 것이 분명합니다.

재귀의 기본 조건은 단지 시간을 절약하는 것입니다. 0으로 돌려 줄 수도 있지만, 그런 다음 코너 사례를 처리해야합니다.

#include<stdio.h> 
long long dp[1000000] = {0}; 

long long max(long long a, long long b){ 
    return a>b?a:b; 
} 

long long coins(long long n){ 
    if (n < 1000000) 
     return dp[n]; 
    return coins(n/2) + coins(n/3) + coins(n/4); 
} 

int main(){ 
for(long long i = 1; i < 1000000; i++){ 
    dp[i] = max(i, dp[i/2] + dp[i/3] + dp[i/4]); 
} 
long long n; 
while(scanf("%lld",&n) != EOF){ 
    printf("%lld\n", coins(n)); 
} 
return 0; 
}