2748번 '피보나치 수 2'

import java.io.*;

class Main{

static long[] d;

public static void main(String[] args) throws IOException {

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

int number = Integer.parseInt(in.readLine());

d = new long[number+1];

System.out.println(solve(number));

in.close();

}

static long solve(int n) {

if(n == 0)

return 0;

else if(n == 1)

return 1;

else if(d[n] > 0)

return d[n];

d[n] = solve(n-1) + solve(n-2);

return d[n];

}

}