SRM 352 DIV1 Easy - NumberofFiboCalls （復習○）
問題
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;
}
};
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;
}
};
