Алгоритам за сликање огради


Ниво на тешкотија Тешко
Често прашувано во CodeNation Facebook Google Интуитивно ЈП Морган Морган Стенли
Низа Динамичко програмирање LeetCode

Изјава за проблем

Во „Алгоритмот за сликање огради“ се вели дека ви е дадена ограда со некои столпчиња (некои дрвени парчиња или некои други парчиња) и некои бои. Откријте бројот на начини да се наслика оградата така што најмногу само 2 соседни огради да имаат иста боја. Бидејќи овој број може да биде голем, вратете го модулот за одговор 1000000007.

пример

Алгоритам за сликање огради

Number of posts/wooden sticks = 2
Number of colors = 2
4

Објаснување
Можете да ги насликате обете објави со различни бои на 2 начини. И имате 2 начини да ги насликате објавите со иста боја. Значи, вкупно имате 4 начини.

Пристап кон сликарскиот алгоритам на оградата

Да почнеме со наивен пристап. Дадени сме дека имаме n објави и k бои. Сега треба да најдеме број на начини на боење на објавите така што да има најмногу само 2 соседни објави со иста боја. Еден наивен пристап може да биде ако ние генерирајте ги сите низи означувајќи ја бојата добиена од секој пост. Но, овој пристап е многу неефикасен и сигурно ќе резултира со надминување на временскиот рок.

Па, што може да биде подобар пристап? Еден пристап би можело да биде ако го разделиме проблемот во помали проблеми. Размислете дека го знаеме одговорот за бројот на објави = n-2 и n-1. Дозволете ни да ги означиме овие вредности користејќи F (n-2) и F (n-1), соодветно. Значи, знаеме дека F (n-1) претставува број на начини на кои најмногу само 2 соседни постови можат да имаат иста боја и истото важи и за F (n-2). Сега сметаме дека ако ги обоиме објавите во (n-1) та и n-та позиција со иста боја, бараме (n-1) th пост да не има иста боја како онаа на (n-2) nd пост. Оваа вредност се означува со употреба на F (n-2). Значи, разгледавме случај кога нашиот n-ти пост има иста боја како и последниот. Треба да ги разгледаме и начините каде тековниот и последниот пост не треба да имаат иста боја. Оваа вредност е означена со употреба на F (n-1). Сега имаме (k-1) начини да го обоиме n-тиот пост. Така, вкупниот број на начини е еднаков на (F (n-1) + F (n-2)) * (k-1).

Код

C ++ код за алгоритам за сликање огради

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

int main(){
  // number of posts
  int n;cin>>n;
  // number of available colors
  int k;cin>>k;
  int mod = 1000000007;
  int ways = 0;
  if(n == 1)cout<<k;
  else if(n == 2)cout<<k*k;
  else {
    int last = k*k; int lastTolast = k;
    for(int i=3;i<=n;i++){
      ways = ((last + lastTolast)*(k-1))%mod;
      lastTolast = last;
      last = ways;
    }
    cout<<ways;
  }
}
4 2
10

Јава код за алгоритам за сликање огради

import java.util.*;
class Main{
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    	// number of posts
    int n = sc.nextInt();
    // number of available colors
    int k = sc.nextInt();
    int mod = 1000000007;
    int ways = 0;
    if(n == 1)System.out.print(k);
    else if(n == 2)System.out.print(k*k);
    else {
      int last = k*k; int lastTolast = k;
      for(int i=3;i<=n;i++){
        ways = ((last + lastTolast)*(k-1))%mod;
        lastTolast = last;
        last = ways;
      }
      System.out.print(ways);
    }
    }
}
4 2
10

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

Временска сложеност

НА), како што можеме да видиме од алгоритмот. Користевме една јамка која работи сè додека i не е еднаква на n. Така, се прават n повторувања, што значи дека имаме линеарна временска сложеност.

Комплексноста на просторот

О (1),  бидејќи сме користеле постојан број на променливи наместо да правиме низа DP. Овој пристап е поисплатлива, бидејќи решението за проблемот зависи само од последните два помали проблеми.