2016-07-08 23 views
-2

私は最近DPの問題を解決し始めました。私はCOINSに出くわしました。私はmemoizationでDPを使って解決しようとしましたが、int配列を使うとうまくいきます(私は推測します)。 は、ここに私のアプローチ(左いくつかの変更)です:SPOJ COINS DPと再帰的アプローチ

#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を取得し、長い長い配列を使用するように私はすぐに理解していません。 私は検索しましたが、私が理解していない再帰的な解決策があるようです。 誰かが私を助けてくれますか?

+0

制限は 'のn <= 10e9'、配列のサイズはその常にメモリオーバーフローになり、したがって、SIGSEGV言う:

正確なコード(あなたはそこに私のポイントを得ます)。あなたのdp-arrayのタイプが何であるかは関係ありません。 – vish4071

答えて

3

制限は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; 
} 
+0

ありがとうございました!それは多くの助けになりました! –

+0

また、これは、n <= 10e9のときに再帰アプローチに従うのが一般的なトリックですか?私の再帰の概念は少し弱いです。 –

+0

ええと...これは時間の多様性を減らします。再帰の基本ケースを選択する必要があります。再帰の深さは最小限に抑えられます。これは再帰が二重の剣であるからです。コード長を減らすのに役立つ限り、再帰スタックが深すぎるとスタックオーバーフローが発生し、SIGSEGVも発生します。 (自分で試してみると、spoj内のどのグラフ問題でも、DFSを使って解決し、(E、V)には良い制限があり、再帰で試してみるとSOが発生します)DFSの同じロジックを繰り返し実行すると、 ) – vish4071