---

這題陷阱在答案可能會超過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解此題。