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


Ниво на трудност Лесно
Често задавани в 24 * 7 иновационни лаборатории Амазонка DE Шоу Делхейвъри PayPal
Динамично програмиране Фибоначи Математически

Декларация за проблема

„Проблемът с облицовката“ гласи, че имате размер на мрежата 2 x 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

Анализ на сложността

Сложност във времето

НА), защото за да се реши проблемът с решетъчната мрежа 2xN. Трябва да сте изчислили отговора за решетка с плочки с размер по-малък от N.

Сложност на пространството

НА), тъй като съхраняваме резултата за всички подпроблеми и по този начин необходимото пространство е линейно.

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