Проблема плитки


Рівень складності Легко
Часто запитують у 24 * 7 Інноваційні лабораторії Амазонка Д. Е. Шоу Делівері PayPal
Динамічне програмування Fibonacci Математика

Постановка проблеми

У "Проблемі з плитками" зазначено, що у вас є сітка розміру 2 х N і плитка розміром 2 х 1. Отже, знайдіть кількість способів викласти плитку даною сіткою.

Приклад

3
2

Пояснення: Проблема плитки

Підхід до проблеми плитки

Ми можемо вирішити цю проблему за допомогою рекурсії. У задачі нам потрібно викласти сітку 2xN. Тож це буде залежати від кількості способів накладання плитки на сітку розміром 2x (N-1) та 2x (N-2). Як ми можемо це сказати?

Причина проста, замість того, щоб думати про плитку першого стовпця в сітці, потім другого тощо. Ми намагаємось спочатку викласти плитку N-ю колонку, потім N-1 тощо. Таким чином знаємо, що якщо ми розмістимо плитку 2 × 1 на N-му стовпці. Тепер ця проблема перетворена на підзадачу розміщення сітки розміру 2x (N-1). Подібним чином, якщо ми розмістимо дві плитки 1 × 2 у сітці 2xN, проблема перетвориться на розмір 2x (N-2). Тепер, якщо ми можемо якось вирішити ці проблеми, ми можемо отримати відповідь.

Скажімо, Tile [N] позначає кількість способів накладання плитки на сітку розміром 2XN. Тоді Плитка [N] = Плитка [N-1] + Плитка [N-2]. Подібним чином, Плитка [N-1] = Плитка [N-2] + Плитка [N-3]. Таким чином, проблема показує оптимальну підструктуру. Краще зберегти результат для Tile [N-2], оскільки він використовується двічі. Якщо ми зберігаємо результат, ми не будемо обчислювати його двічі і значно зменшимо складність часу. Таким чином ми будемо використовувати Динамічне програмування вирішити проблему.

Проблема плитки

код

Код C ++ для проблеми плитки

#include<bits/stdc++.h> 
using namespace std; 

int main(){
  int n;cin>>n;
  // create an array to store number of ways to tile a grid of size 2xi
  int tile[n+1];
  // base case
  tile[0] = 0; tile[1] = 1;
  for(int i=2;i<=n;i++)
    tile[i]  = tile[i-1] + tile[i-2]; // use recursive formula
  cout<<tile[n];
}
3
2

Код Java для проблеми плитки

import java.util.*;

class Main{
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    // create an array to store number of ways to tile a grid of size 2xi
    int tile[] = new int[n+1];
    // base case
    tile[0] = 0; tile[1] = 1;
    for(int i=2;i<=n;i++)
      tile[i]  = tile[i-1] + tile[i-2]; // use recursive formula
    System.out.println(tile[n]);
  }
}
3
2

Аналіз складності

Складність часу

O (N), тому що для того, щоб вирішити проблему укладання плитки сітки 2xN. Вам потрібно було розрахувати відповідь для сітки плитки розміром менше N.

Складність простору

O (N), оскільки ми зберігаємо результат для всіх підзадач і, отже, необхідний простір є лінійним.

Примітка: Ми можемо вирішити проблему в просторі O (1) та O (N), використовуючи дві змінні last і secondLast, які зберігатимуть значення Tile [N-1] та Tile [N-2] відповідно. Тепер current = last + secondLast, а потім оновіть значення змінних відповідно. Рекурсивна формула така ж, як і формула N-го числа Фібоначчі. Отже, ви також можете вирішити цю проблему за O (log N) час, використовуючи формулу для пошуку чисел Фібоначчі.