[7급 국가직 알고리즘 2025년 22번]

동적 프로그래밍은 한 번 계산된 값을 메모리에 저장한 후, 저장된 값을 필요할 때마다 가져다 쓰는 방법이다. 동적 프로그래밍을 적용하여 구현한 다음 Java 프로그램에서 피보나치 수열 fibo(6)을 구하기 위해 저장되어 있는 fibo(3)의 결과를 가져다 쓰는 횟수는?

public class Fibonacci {
	static int[] dp = new int[100];

	public static void main(String[] args) {
		System.out.println(fibo(6));
	}

	public static int fibo(int num) {
		if(num == 0) {
			return 0;
		}
		if(num == 1) {
			return 1;
		}
		if(dp[num] != 0) {
			return dp[num];
		}
		return dp[num] = fibo(num - 1) + fibo(num - 2);
	}
}