白準10826号:フィボナッチ数4

問題の説明

https://www.acmicpc.net/problem/10826

これは

フィボナッチの数字を求める問題です.

方法

メモテクノロジーを使用して、問題を解決できます.

失いやすいところ

Nが0の場合を考えるべきです.

の数字はとても大きいと思います.

longも足りません.

てんかしき

dp[i]=dp[i−1]+dp[i−2]dp[i] = dp[i-1]+dp[i-2]dp[i]=dp[i−1]+dp[i−2]

正解

import java.util.*;
import java.math.BigInteger;


public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		BigInteger[] dp = new BigInteger[N+2];
		
		dp[0] = new BigInteger("0");
		dp[1] = new BigInteger("1");
		for (int i = 2; i < dp.length; i++) {
			dp[i] = dp[i-1].add(dp[i-2]);
		}
		System.out.println(dp[N]);
	}
}