चित्रकारी फेंस एल्गोरिथ्म


कठिनाई तह हार्ड
बारम्बार सोधिन्छ CodeNation फेसबुक गुगल Intuit जेपी मोर्गन मोर्गन स्टेनले
एरे डायनामिक प्रोग्रामिंग LeetCode

समस्या वक्तव्य

"पेंटिंग फेंस एल्गोरिथ्म" ले बताउँदछ कि तपाईंलाई केही पोष्टहरू (केही काठका टुक्रा वा केहि अन्य टुक्राहरू) र केही रंगहरू सहित एउटा बार दिइन्छ। बारमा र paint लगाउने तरिकाहरूको संख्या पत्ता लगाउनुहोस् कि अधिकतम २ आसन्न बाडमा समान रंग हुन्छ। किनकि यो संख्या ठूलो हुन सक्छ, जवाफ मोडुलु १०००००००००2 फिर्ता गर्नुहोस्।

उदाहरणका

चित्रकारी फेंस एल्गोरिथ्म

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

स्पष्टीकरण
तपाई दुबै पोष्टहरुलाई बिभिन्न रंगहरु संग २ तरीकाले रंग्न सक्नुहुन्छ। र तपाईंसँग उही र postsको साथ पोष्टहरू रंगाउन २ तरिकाहरू छन्। त्यसैले कुल तपाईं 2 तरिका छ।

पेन्टिंग फेंस एल्गोरिथ्मको लागि दृष्टिकोण

एक भोली दृष्टिकोण संग सुरू गरौं। हामीलाई दिइएको छ कि हामीसँग n पोष्ट र के रंगहरू छन्। अब हामीले पोष्टहरू र color्ग गर्ने तरिकाहरूको संख्या पत्ता लगाउन आवश्यक छ जुन समान रंगको साथ अधिकतम २ आसन्न पोष्टहरू छन्। एउटा भोली दृष्टिकोण हुन सक्छ यदि हामी सबै अनुक्रम उत्पन्न गर्नुहोस् प्रत्येक पोष्ट द्वारा प्राप्त र color्ग संकेत गर्दै। तर यो दृष्टिकोण अत्यधिक अक्षम छ र निश्चित रूपमा समय सीमा नाघ्ने परिणाम दिनेछ।

त्यसोभए, राम्रो तरिका के हुन सक्छ? एक दृष्टिकोण हुनसक्छ यदि हामीले समस्यालाई साना समस्यामा पार्छौं भने। विचार गर्नुहोस् कि हामीलाई पोष्टहरूको संख्या = n-2 र n-1 को लागी जवाफ थाहा छ। हामी यी मानहरू क्रमश: F (n-2) र F (n-1) को प्रयोग गरी देखाउन सक्छौं। त्यसोभए हामी जान्दछौं कि एफ (n-1) ले ती तरीकाहरूको संख्या प्रतिनिधित्व गर्दछ जहाँ अधिकतम २ आसन्न पोष्टहरूमा समान रंग हुन सक्छ र समान F (n-2) को लागी हुन्छ। अब हामी विचार गर्छौं कि यदि हामी (n-2) th र nth स्थितिमा उही र color्गका साथ र ,्ग गर्छौं भने, हामीलाई यो आवश्यक हुन्छ कि (n-1) th पोष्टको (n-1) nd पोष्टको जस्तो रंग हुन हुँदैन। यो मान एफ (n-2) को उपयोग गरेर दर्साइएको छ। यसैले हामीले एउटा केसमा विचार ग .्यौं जहाँ हाम्रो nth पोस्टमा अन्तिम पोष्टको समान रंग छ। हामीले ती तरिकाहरू पनि विचार गर्नुपर्दछ जहाँ हालको पोष्ट र अन्तिम पोष्टमा समान रंग हुँदैन। यो मान एफ (n-2) को प्रयोग गरेर दर्साइएको छ। अब हामीसँग (k-1) तरीका छन् एनटी पोष्टलाई रंग गर्न। यसरी तरिकाको कुल संख्या बराबर छ (F (n-1) + F (n-1)) * (k-2)।

कोड

चित्रकारी फेंस एल्गोरिथ्मको लागि 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

जटिलता विश्लेषण

समय जटिलता

O (N), जस्तो कि हामी एल्गोरिथ्मबाट देख्न सक्छौं हामीले एकल लूप प्रयोग गरेका छौं जुन i को n बराबर नभएसम्म चल्छ। यसैले एन पुनरावृत्तिहरू बनाउने, जसको मतलब हामीसँग लाइनर समय जटिलता छ।

ठाउँ जटिलता

O (१),  किनकि हामीले DP एर्रे बनाउनुको सट्टा भ्यारीएबलको स्थिर संख्या प्रयोग गर्यौं। यो दृष्टिकोण अधिक व्यवहार्य हो किनकि समस्याको समाधान अन्तिम दुई सानो समस्यामा मात्र निर्भर गर्दछ।