SRM 352 DIV1 Easy - NumberofFiboCalls

SRM 352 DIV1 Easy - NumberofFiboCalls

9:29

問題


http://community.topcoder.com/stat?c=problem_statement&pm=2292&rd=10709

フィボナッチ数の計算が再帰プログラムで書かれている。

このとき、ある整数ｎのフィボナッチ数を求めるときに再帰プログラムにて１と０が出力される回数を求める。

解き方


ｎの最大が４０のため全探索では解くことができない。

ここで、ある数xまでに出力される０と１の回数もフィボナッチ数と同様に、
x-1とあるx-2の０と１の回数の和で求められることがわかる。

これをｄｐで実装する。

コード


class NumberofFiboCalls {

public: vector<int> fiboCallsMade(int n) {
vector<int> ans;
int dp0[n+1],dp1[n+1];

memset(dp0,0,sizeof(dp0));
memset(dp1,0,sizeof(dp1));

dp0[0]=1,dp1[1]=1;

FORE(i,2,n+1){
dp0[i]=dp0[i-1]+dp0[i-2];
dp1[i]=dp1[i-1]+dp1[i-2];
}
ans.push_back(dp0[n]);
ans.push_back(dp1[n]);

return ans;
}

};

Share this

Google Facebook Twitter More

Related Posts