Lát gạch 2*n

Đề bài: http://vn.spoj.com/problems/LATGACH/

Đầu tiên ta xét hình chữ nhật 2×1 thì có 1 cách xếp đó là xếp 1 viên gạch 2×1.
Xét hình chữ nhật 2×2 thì có 2 cách xếp đó là xếp 2 viên 1×2 hoặc 2 viên 2×1.
Xét hình chữ nhật 2xi có các trường hợp sau với f(i) là số cách xếp cho hình chữ nhật 2xi.

=> f(i) = f(i-1) + f(i-2) với f(1) = 1 và f(2) = 2
=> f(N) là kết quả của bài toán
Công thức truy hồi trên chính là công thức của dãy Fibonacy nổi tiếng.
Giới hạn của bài này là N<=100, do đó f(N) sẽ rất lớn ta phải sử dụng cách cộng số lớn theo kiểu cộng mảng các chữ số.

Một số bài lát gạch khác:
Lát gạch 3*n
Và tham khảo thêm: HOLEY SQUARE – Robert Tauraso