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; 
}