Task 45. Положить плитку

Задача: Коридор NxM метров нужно застелить N плитками 1xM метров, чтобы не было не застеленной поверхности. Нужно написать функцию, ктр найдет кол-во способов это сделать.

Например, для коридора 6x4 метра существует 4-е способа застелить плитками 1x4 (см.схематический рисунок).

Идея: задача из раздела динамического программирования, так как по сути нужно найти кол-во всевозможных способов.

Обозначим, A(n) - кол-во способов застелить коридор длиной n. Так как для коридора длиной k (где k < m) плитки можно укладывать только по ширине (горизонтально), то A(k) = 1.

Для других случаев плитки в последнем ряду можно положить или горизонтально или вертикально, поэтому мы получаем следующую формулу:

A(n) = A(n - 1) + A(n - m)

Реализация:

https://gist.github.com/unilecs/08c47fdaea8fa3902affc4eb2b2f023e

Тест:

https://dotnetfiddle.net/lnEMh9