ਪੇਂਟਿੰਗ ਵਾੜ ਐਲਗੋਰਿਦਮ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਹਾਰਡ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਕੋਡਨੇਸ਼ਨ ਫੇਸਬੁੱਕ ਗੂਗਲ Intuit JP Morgan ਮੋਰਗਨ ਸਟੈਨਲੇ
ਅਰੇ ਡਾਇਨਾਮਿਕ ਪ੍ਰੋਗਰਾਮਿੰਗ LeetCode

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ

“ਪੇਂਟਿੰਗ ਫੈਂਸ ਐਲਗੋਰਿਦਮ” ਕਹਿੰਦਾ ਹੈ ਕਿ ਤੁਹਾਨੂੰ ਇੱਕ ਵਾੜ ਦਿੱਤੀ ਗਈ ਹੈ ਜਿਸ ਵਿੱਚ ਕੁਝ ਪੋਸਟਾਂ ਹਨ (ਕੁਝ ਲੱਕੜ ਦੇ ਟੁਕੜੇ ਜਾਂ ਕੁਝ ਹੋਰ ਟੁਕੜੇ) ਅਤੇ ਕੁਝ ਰੰਗ. ਵਾੜ ਨੂੰ ਪੇਂਟ ਕਰਨ ਦੇ waysੰਗਾਂ ਦੀ ਗਿਣਤੀ ਕਰੋ ਜਿਵੇਂ ਕਿ ਵੱਧ ਤੋਂ ਵੱਧ ਸਿਰਫ 2 ਨਾਲ ਲੱਗਦੇ ਵਾੜ ਇਕੋ ਰੰਗ ਦੇ ਹੋਣ. ਕਿਉਂਕਿ ਇਹ ਗਿਣਤੀ ਵੱਡੀ ਹੋ ਸਕਦੀ ਹੈ, ਇਸ ਲਈ ਜਵਾਬ ਮੋਡੀulਲੋ 1000000007 ਵਾਪਸ ਕਰੋ.

ਉਦਾਹਰਨ

ਪੇਂਟਿੰਗ ਵਾੜ ਐਲਗੋਰਿਦਮ

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

ਕਥਾ
ਤੁਸੀਂ ਦੋਹਾਂ ਪੋਸਟਾਂ ਨੂੰ 2 ਤਰੀਕਿਆਂ ਨਾਲ ਵੱਖ ਵੱਖ ਰੰਗਾਂ ਨਾਲ ਪੇਂਟ ਕਰ ਸਕਦੇ ਹੋ. ਅਤੇ ਤੁਹਾਡੇ ਕੋਲ ਉਸੇ ਰੰਗ ਨਾਲ ਪੋਸਟਾਂ ਨੂੰ ਪੇਂਟ ਕਰਨ ਲਈ 2 ਤਰੀਕੇ ਹਨ. ਇਸ ਲਈ ਕੁੱਲ ਤੁਹਾਡੇ ਕੋਲ 4 ਤਰੀਕੇ ਹਨ.

ਪੇਂਟਿੰਗ ਵਾੜ ਐਲਗੋਰਿਦਮ ਲਈ ਪਹੁੰਚ

ਆਓ ਇੱਕ ਭੋਲੇਪਣ ਦੀ ਪਹੁੰਚ ਨਾਲ ਸ਼ੁਰੂਆਤ ਕਰੀਏ. ਸਾਨੂੰ ਦਿੱਤਾ ਗਿਆ ਹੈ ਕਿ ਸਾਡੇ ਕੋਲ n ਪੋਸਟਾਂ ਅਤੇ ਕੇ ਰੰਗ ਹਨ. ਹੁਣ ਸਾਨੂੰ ਪੋਸਟਾਂ ਨੂੰ ਰੰਗ ਕਰਨ ਦੇ waysੰਗਾਂ ਦੀ ਗਿਣਤੀ ਲੱਭਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ ਕਿ ਇਕੋ ਰੰਗ ਦੇ ਨਾਲ ਘੱਟੋ ਘੱਟ ਸਿਰਫ 2 ਲਗਭਗ ਪੋਸਟਾਂ ਹਨ. ਇਕ ਭੋਰਾ ਜਿਹਾ ਪਹੁੰਚ ਹੋ ਸਕਦਾ ਹੈ ਜੇ ਅਸੀਂ ਸਾਰੇ ਕ੍ਰਮ ਤਿਆਰ ਕਰੋ ਹਰੇਕ ਪੋਸਟ ਦੁਆਰਾ ਪ੍ਰਾਪਤ ਕੀਤੇ ਰੰਗ ਨੂੰ ਦਰਸਾਉਂਦਾ ਹੈ. ਪਰ ਇਹ ਪਹੁੰਚ ਬਹੁਤ ਅਸਮਰਥ ਹੈ ਅਤੇ ਨਿਸ਼ਚਤ ਤੌਰ ਤੇ ਸਮਾਂ ਸੀਮਾ ਤੋਂ ਵੱਧ ਜਾਵੇਗੀ.

ਤਾਂ ਫਿਰ ਇਸ ਤੋਂ ਵਧੀਆ ਪਹੁੰਚ ਕੀ ਹੋ ਸਕਦੀ ਹੈ? ਇਕ ਪਹੁੰਚ ਹੋ ਸਕਦਾ ਹੈ ਜੇ ਅਸੀਂ ਸਮੱਸਿਆ ਨੂੰ ਛੋਟੀਆਂ ਮੁਸ਼ਕਲਾਂ ਵਿਚ ਵੰਡ ਦੇਈਏ. ਵਿਚਾਰ ਕਰੋ ਅਸੀਂ ਅਸਾਮੀਆਂ ਦੀ ਗਿਣਤੀ ਦਾ ਜਵਾਬ ਜਾਣਦੇ ਹਾਂ = n-2 ਅਤੇ n-1. ਚਲੋ ਕ੍ਰਮਵਾਰ F (n-2) ਅਤੇ F (n-1) ਦੀ ਵਰਤੋਂ ਕਰਦੇ ਹੋਏ ਇਨ੍ਹਾਂ ਵੈਲਯੂਜ ਨੂੰ ਦਰਸਾਓ. ਇਸ ਲਈ ਅਸੀਂ ਜਾਣਦੇ ਹਾਂ ਕਿ F (n-1) ਉਹਨਾਂ ਤਰੀਕਿਆਂ ਦੀ ਸੰਖਿਆ ਨੂੰ ਦਰਸਾਉਂਦਾ ਹੈ ਜਿਸ ਵਿੱਚ ਵੱਧ ਤੋਂ ਵੱਧ ਸਿਰਫ 2 ਲਾਗਲੀਆਂ ਪੋਸਟਾਂ ਵਿੱਚ ਇੱਕੋ ਰੰਗ ਹੋ ਸਕਦਾ ਹੈ ਅਤੇ F (n-2) ਲਈ ਇਹ ਸੱਚ ਹੈ. ਹੁਣ ਅਸੀਂ ਵਿਚਾਰ ਕਰਦੇ ਹਾਂ ਕਿ ਜੇ ਅਸੀਂ (n-1) th ਅਤੇ nth ਸਥਿਤੀ 'ਤੇ ਇਕੋ ਰੰਗ ਨਾਲ ਪੋਸਟਾਂ ਨੂੰ ਰੰਗਦੇ ਹਾਂ, ਤਾਂ ਸਾਨੂੰ ਇਸ ਦੀ ਜ਼ਰੂਰਤ ਹੈ ਕਿ (n-1) th ਦੀ ਪੋਸਟ (n-2) nd ਪੋਸਟ ਵਾਂਗ ਨਹੀਂ ਹੋਣੀ ਚਾਹੀਦੀ. ਇਹ ਮੁੱਲ ਐਫ (ਐਨ -2) ਦੀ ਵਰਤੋਂ ਨਾਲ ਦਰਸਾਇਆ ਗਿਆ ਹੈ. ਇਸ ਲਈ ਅਸੀਂ ਇੱਕ ਅਜਿਹੇ ਕੇਸ ਬਾਰੇ ਵਿਚਾਰ ਕੀਤਾ ਹੈ ਜਿੱਥੇ ਸਾਡੀ ਐਨਵੀ ਪੋਸਟ ਦੀ ਆਖਰੀ ਪੋਸਟ ਵਰਗੀ ਰੰਗ ਹੈ. ਸਾਨੂੰ ਉਨ੍ਹਾਂ ਤਰੀਕਿਆਂ ਬਾਰੇ ਵੀ ਵਿਚਾਰ ਕਰਨਾ ਚਾਹੀਦਾ ਹੈ ਜਿੱਥੇ ਮੌਜੂਦਾ ਪੋਸਟ ਅਤੇ ਆਖਰੀ ਪੋਸਟ ਦਾ ਰੰਗ ਇੱਕੋ ਜਿਹਾ ਨਹੀਂ ਹੋਣਾ ਚਾਹੀਦਾ. ਇਹ ਮੁੱਲ ਐਫ (ਐਨ -1) ਦੀ ਵਰਤੋਂ ਨਾਲ ਦਰਸਾਇਆ ਗਿਆ ਹੈ. ਹੁਣ ਸਾਡੇ ਕੋਲ nth ਪੋਸਟ ਨੂੰ ਕਲਰ ਕਰਨ ਦੇ ਤਰੀਕੇ (ਕੇ -1) ਹਨ. ਇਸ ਪ੍ਰਕਾਰ ਤਰੀਕਿਆਂ ਦੀ ਕੁਲ ਗਿਣਤੀ (ਐਫ (ਐਨ -1) + ਐੱਫ (ਐਨ -2)) * (ਕੇ -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

ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਸਮੇਂ ਦੀ ਜਟਿਲਤਾ

ਓ (ਐਨ), ਜਿਵੇਂ ਕਿ ਅਸੀਂ ਐਲਗੋਰਿਦਮ ਤੋਂ ਦੇਖ ਸਕਦੇ ਹਾਂ. ਅਸੀਂ ਇਕੋ ਲੂਪ ਇਸਤੇਮਾਲ ਕੀਤਾ ਹੈ ਜੋ ਚੱਲਦਾ ਹੈ ਜਦ ਤਕ ਮੈਂ n ਦੇ ਬਰਾਬਰ ਨਹੀਂ ਹੁੰਦਾ. ਇਸ ਤਰ੍ਹਾਂ n ਦੁਹਰਾਓ ਬਣਾਉਣਾ, ਜਿਸਦਾ ਅਰਥ ਹੈ ਕਿ ਸਾਡੇ ਕੋਲ ਰੇਖਿਕ ਸਮੇਂ ਦੀ ਜਟਿਲਤਾ ਹੈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (1),  ਜਿਵੇਂ ਕਿ ਅਸੀਂ ਡੀਪੀ ਐਰੇ ਬਣਾਉਣ ਦੀ ਬਜਾਏ ਨਿਰੰਤਰ ਗਿਣਤੀ ਵਿੱਚ ਪਰਿਵਰਤਨ ਵਰਤੇ ਹਨ. ਇਹ ਪਹੁੰਚ ਵਧੇਰੇ ਵਿਹਾਰਕ ਹੈ ਕਿਉਂਕਿ ਸਮੱਸਿਆ ਦਾ ਹੱਲ ਸਿਰਫ ਪਿਛਲੇ ਦੋ ਛੋਟੀਆਂ ਮੁਸ਼ਕਲਾਂ 'ਤੇ ਨਿਰਭਰ ਕਰਦਾ ਹੈ.