Now, I solved a DP problem.

Dynamic programming is one of the problem-solving methods. this method divides a problem to sub-problems. It stores a result of the algorithm by specific values to the memory for reusing. So When that value occurs, We can use that data again. Thus we can optimize re-computing time.

### Problem

Following source code is C++ function for calculating N

Fibonacci number.

```
int fibonacci(int n) {
if (n == 0) {
printf("0");
return 0;
} else if (n == 1) {
printf("1");
return 1;
} else {
return fibonacci(n‐1) + fibonacci(n‐2);
}
}
```

When fibonacci(3) is called, it would be worked like this:

- fibonacci(3) call fibonacci(2) and fibonacci(1)(first called).
- fibonacci(2) call fibonacci(1)(second called) and fibonacci(0).
- fibonacci(1)(second called) return and print 1.
- fibonacci(0) return and print 0.
- fibonacci(2) get result of fibonacci(1) and fibonacci(0) and return 1.
- fibonacci(1)(fist called) return and print 1.
- fibonacci(3) get result of fibonacci(2) and fibonacci(1) and return 2.

Thus, number 1 printed the twice and 0 printed a single.

Write a program to calculate how many number 0 and 1 printed when number N is given.

**Time limit: 0.25 Second**

### Input

The value T will be given that is the count of test-case. Each case consists of a single line which is number N. (0<=N<=40)

### Output

Print the numbers of the count of 0 and 1 which is separated by the white-space.

### Example Input

```
3
0
1
3
```

### Example Output

```
1 0
0 1
1 2
```

From here

When I met this problem the first time, I just used counting 0 and 1.

But my counting method always made the time-over.

I had some few times for thinking. The main topic is calculation time.

And the following idea occurred to me.

**If I store the value of fibonacci(N) to reuse?**

If I do that, This algorithm makes calculation just a single time by the N value.

So I fixed above function like this.

```
int DP[41] = {0};
int fibonacci(int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
if(DP[n]!=0)
return DP[n];
else
{
int res = fibonacci(n-1) + fibonacci(n-2);
DP[n] = res;
return res;
}
}
}
```

If fibonacci(2) called the first time, it would call fibonacci(1) and fibonacci(0) functions which just return 1 and 0. And then it stored the result of fibbonacci(2) to DP[2].

Thus, when fibonacci function called next time, it would return the value of DP[2].

So It’s solved!

But let’s see the problem.

We need to count how many 0 and 1 is printed.

But we can’t count use counter because every function by N is called a single time.

Let’s think.

We need to find how many N value consists of 1 and 0 makes function-call.

Let’s think when fibonacci(2) is called.

fibonacci(2) makes fibonacci(1) and fibonacci(0).

As you can see that makes counting each 1 and 0 by specific value N=2.

Thus, We can make this formula:

zero_count = { 1, 0, 0 …} zero_count[N] = zero_count[N-1] + zero_count[N-2]

one_count { 0, 1, 0 …} one_count[N] = one_count[N-1] + one_count[N-2]

So If I use above to source code, we can solve finally.

```
#include <iostream>
using namespace std;
int DP[41] = {0};
int DPC[41] = {0,1,0,};
int DPZC[41] = {1,0,};
int fibonacci(int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
if(DP[n]!=0)
return DP[n];
else
{
int res = fibonacci(n-1) + fibonacci(n-2);
DPC[n] = DPC[n-1] + DPC[n-2];
DPZC[n] = DPZC[n-1] + DPZC[n-2];
DP[n] = res;
return res;
}
}
}
int main()
{
int T,N;
cin.sync_with_stdio(false);
cout.sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>T;
for(int i=0;i<T;i++)
{
cin>>N;
fibonacci(N);
cout<<DPZC[N]<<" "<<DPC[N]<<'\n';
}
return 0;
}
```

I heard DP method but I couldn’t use that.

And luckily I can deploy that method through this problem!