Նկարչական ցանկապատի ալգորիթմ  


Դժվարության մակարդակ Դժվար
Հաճախակի հարցնում են CodeNation facebook Google Intuit JP Morgan Morgan Stanley
Դասավորություն Դինամիկ ծրագրավորում LeetCode

Խնդիրի հայտարարություն  

«Նկարչական ցանկապատի ալգորիթմը» նշում է, որ ձեզ տրվում է ցանկապատ, որն ունի որոշ հենարաններ (որոշ փայտե կտորներ կամ որոշ այլ կտորներ) և որոշ գույներ: Բացահայտեք ցանկապատը նկարելու եղանակների քանակը այնպես, որ առավելագույնը միայն հարակից 2 ցանկապատերը ունենան նույն գույնը: Քանի որ այս թիվը կարող է մեծ լինել, վերադարձիր 1000000007 պատասխանի մոդուլը:

Օրինակ  

Նկարչական ցանկապատի ալգորիթմPin

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

բացատրություն
Երկու գրառումները կարող եք նկարել տարբեր գույներով ՝ 2 եղանակով: Եվ դուք ունեք նույն գույնով գրառումները ներկելու 2 եղանակ: Այսպիսով, ընդհանուր առմամբ դուք ունեք 4 եղանակ:

Fանկապատի ալգորիթմի նկարչության մոտեցում  

Սկսենք միամիտ մոտեցումից: Մեզ տալիս են, որ մենք ունենք 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) - ի գրառումը չպետք է ունենա նույն գույնը, ինչ (n-2) - ի երկրորդ գրառմանը: Այս արժեքը նշվում է օգտագործելով F (n-2): Այսպիսով, մենք քննարկել ենք մի դեպք, երբ մեր n- րդ գրառումն ունի նույն գույնը, ինչ վերջին գրառմանը: Մենք պետք է հաշվի առնենք նաև այն եղանակները, երբ ընթացիկ հաղորդագրությունը և վերջին հաղորդագրությունը չպետք է ունենան նույն գույնը: Այս արժեքը նշվում է օգտագործելով F (n-1): Այժմ մենք ունենք (k-1) եղանակներ nth գրառումը գունավորելու համար: Այսպիսով, ճանապարհների ընդհանուր քանակը հավասար է (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

Նկարչական ցանկապատի ալգորիթմի Java- ի կոդ

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

Բարդության վերլուծություն  

Timeամանակի բարդությունը

ՎՐԱ), ինչպես տեսնում ենք ալգորիթմից: Մենք օգտագործել ենք մեկ օղակ, որն անցնում է մինչև i- ը հավասար է n- ի: Այսպիսով կատարելով n կրկնություն, ինչը նշանակում է, որ մենք ունենք գծային ժամանակի բարդություն:

Տիեզերական բարդություն

O (1),  քանի որ մենք օգտագործել ենք հաստատուն թվով փոփոխականներ ՝ փոխարենը կազմելով DP զանգված: Այս մոտեցումն առավել կենսունակ է, քանի որ խնդրի լուծումը կախված է միայն վերջին երկու փոքր խնդիրներից: