#32186: C++ 遞迴與DP解法比較


ostriich_LEN (駱駝)

School : 國立嘉義大學
ID : 148499
IP address : [120.113.180.120]
Last Login :
2024-03-28 15:57:43
a216. 數數愛明明 | From: [59.127.42.125] | Post Date : 2022-09-19 19:50

這題陷阱在答案可能會超過int範圍,不管用哪種解法務必使用long long宣告。

遞迴解:

#include <bits/stdc++.h>

using namespace std;

 

long long g(long long n);

long long f(long long n);

 

long long g(long long n){

if (n==1)

return 1;

else

return f(n)+g(n-1);

}

 

long long f(long long n){

if(n==1)

return 1;

else

return n+f(n-1);

}

 

int main(){

long long n;

while (cin>>n && n!=EOF){

cout <<f(n)<<' '<<g(n)<<'\n';

}

return 0;

}

 

 

DP解:

#include <bits/stdc++.h>

using namespace std;

 

int main(){

int n;

long long f[30001];

long long g[30001];

f[1]=1;

g[1]=1;

 

for (long long i=2;i<=30000;i++){

f[i]=i+f[i-1];

}

for (long long i=2;i<=30000;i++){

g[i]=f[i]+g[i-1];

}

 

while (cin>>n && n!=EOF){

cout <<f[n]<<' '<<g[n]<<'\n';

}

return 0;

}

註:陣列index30000實際為第30001個,因此宣告陣列時大小需>=30001。

 

用CP Editor 跑兩種解法,在n=30000時遞迴解耗時3001ms,DP解耗時68ms。

建議還是以DP解此題。

 

 
ZeroJudge Forum