पेंटिंग बाड़ एल्गोरिथ्म  


कठिनाई स्तर कठिन
में अक्सर पूछा कोडेशन Facebook गूगल सहज जेपी मॉर्गन मॉर्गन स्टेनली
ऐरे गतिशील प्रोग्रामिंग लेटकोड

समस्या का विवरण  

"पेंटिंग बाड़ एल्गोरिथ्म" में कहा गया है कि आपको कुछ पोस्ट (कुछ लकड़ी के टुकड़े या कुछ अन्य टुकड़े) और कुछ रंगों वाले बाड़ दिए जाते हैं। बाड़ को पेंट करने के तरीकों की संख्या का पता लगाएं जैसे कि केवल 2 आसन्न बाड़ में एक ही रंग है। चूंकि यह संख्या बड़ी हो सकती है, उत्तर modulo 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) वें और nth स्थान पर रंग पोस्ट करते हैं, तो हमें आवश्यकता है कि (n-1) वें पोस्ट में n (पोस्ट -2) के समान रंग नहीं होना चाहिए। यह मान F (n-2) का उपयोग करके दर्शाया गया है। इसलिए हमने एक ऐसे मामले पर विचार किया है, जहां हमारी nth पोस्ट का रंग पिछले पोस्ट की तरह ही है। हमें उन तरीकों पर भी विचार करना चाहिए जहां वर्तमान पोस्ट और अंतिम पोस्ट में समान रंग नहीं होना चाहिए। यह मान F (n-1) का उपयोग करके दर्शाया गया है। अब हमारे पास (k-1) nth पोस्ट को कलर करने के तरीके हैं। इस प्रकार कुल तरीकों की संख्या (F (n-1) + F (n-2)) * (k-1) के बराबर है।

यह भी देखें
डिकोड तरीके

कोड  

चित्रकला बाड़ एल्गोरिथ्म के लिए सी ++ कोड

#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

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

समय की जटिलता

पर), जैसा कि हम एल्गोरिथ्म से देख सकते हैं। हमने एक लूप का उपयोग किया है जो तब तक चलता है जब तक कि मैं n के बराबर न हो। इस प्रकार n पुनरावृत्तियों को बनाना, जिसका अर्थ है कि हमारे पास रैखिक समय जटिलता है।

अंतरिक्ष की जटिलता

ओ (1),  जैसा कि हमने DP सरणी बनाने के बजाय निरंतर संख्या में चर का उपयोग किया है। यह दृष्टिकोण अधिक व्यवहार्य है क्योंकि समस्या का समाधान केवल अंतिम दो छोटी समस्याओं पर निर्भर है।