bottom-top으로 생각해보자.
자릿수가 N인 수는 N-1자릿 수 뒤에 0 또는 1이 추가된 경우의 수의 합이다. 이 때, 맨 뒷자리가 0이 되려면, 그 앞자리는 0이든 1이든 상관없다.
따라서 [N-1]자릿수가 그 경우의 수. 하지만, 1이 오려면, 무조건 0이 오고, 그 앞수는 상관이 없다.
따라서 [N-2]자릿수가 그 경우의 수. 결국에 [N] = [N-1] + [N-2] 이므로, 피보나치 수열과 같은 규칙이다.

C++ 코드(bottom-top)

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

long arr[100] = { 0,1 };

int main() {

	int n = 0;
	scanf("%d", &n);
	for (int i = 2; i <= n; i++) arr[i] = arr[i - 1] + arr[i - 2];
	printf("%lld", arr[n]);
}

C# 코드

using System.Text;
using System;
using static System.Console;

class Program
{
    static long[] arr = new long[91];         //1부터 제곱수 들어갈 행렬
    public static void Main(string[] args)
    {
        int n = int.Parse(ReadLine());
        arr[1] = 1;
        for(int i = 2; i<= n; i++)
        {
            arr[i] = arr[i - 1] + arr[i - 2];
        }

        Write(arr[n]);


    }
}

Java 코드

import java.util.*;

public class Main {
    static long[] arr = new long[91];

    public static void main(String[] args) {

        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        arr[1] = 1;

        for(int i = 2; i<= n; i++){
            arr[i] = arr[i-1] + arr[i-2];
        }

        System.out.println(arr[n]);
    }

}

Kotlin 코드

import java.util.*
import kotlin.math.*

fun main(args: Array<String>){
    val arr = LongArray(91)
    arr[1] = 1

    val s = Scanner(System.`in`)
    val input = s.nextInt()

    for(i in 2..input){
        arr[i] = arr[i-1] + arr[i-2]
    }

    print(arr[input])

}

Python 코드

x = int(input())

arr = [0 for _ in range(91)]
arr[1] = 1
for i in range(2, x+1):
    arr[i] = arr[i-1] + arr[i-2]

print(arr[x])