പെയിന്റിംഗ് ഫെൻസ് അൽഗോരിതം


വൈഷമ്യ നില ഹാർഡ്
പതിവായി ചോദിക്കുന്നു കോഡ്നേഷൻ ഫേസ്ബുക്ക് ഗൂഗിൾ Intuit ജെപി മോർഗൻ മോർഗൻ സ്റ്റാൻലി
അറേ ഡൈനാമിക് പ്രോഗ്രാമിംഗ് ലീട്ട് കോഡ്

പ്രശ്നം പ്രസ്താവന

“പെയിന്റിംഗ് ഫെൻസ് അൽ‌ഗോരിതം” പറയുന്നത് നിങ്ങൾക്ക് കുറച്ച് പോസ്റ്റുകളും (ചില തടി കഷണങ്ങൾ അല്ലെങ്കിൽ മറ്റ് ചില കഷണങ്ങളും) ചില നിറങ്ങളുമുള്ള ഒരു വേലി നൽകിയിട്ടുണ്ട്. വേലി വരയ്ക്കുന്നതിനുള്ള മാർഗ്ഗങ്ങളുടെ എണ്ണം കണ്ടെത്തുക, അതായത് സമീപത്തുള്ള 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) th, n സ്ഥാനങ്ങളിൽ ഒരേ വർ‌ണ്ണത്തിൽ‌ ഞങ്ങൾ‌ പോസ്റ്റുകൾ‌ കളർ‌ ചെയ്യുകയാണെങ്കിൽ‌, (n-1) th പോസ്റ്റിന്‌ (n-2) nd പോസ്റ്റിന്‌ സമാനമായ വർ‌ണ്ണമുണ്ടാകരുത് എന്ന് ഞങ്ങൾ‌ ആവശ്യപ്പെടുന്നു. ഈ മൂല്യം F (n-2) ഉപയോഗിച്ച് സൂചിപ്പിക്കുന്നു. അതിനാൽ, ഞങ്ങളുടെ ഒൻപതാമത്തെ പോസ്റ്റിന് അവസാന പോസ്റ്റിന് സമാനമായ നിറമുള്ള ഒരു കേസ് ഞങ്ങൾ പരിഗണിച്ചു. നിലവിലെ പോസ്റ്റിനും അവസാന പോസ്റ്റിനും ഒരേ നിറം ഉണ്ടാകാതിരിക്കാനുള്ള വഴികളും ഞങ്ങൾ പരിഗണിക്കണം. ഈ മൂല്യം 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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N), അൽ‌ഗോരിതം നിന്ന് നമുക്ക് കാണാനാകുന്നതുപോലെ. ഞാൻ n ന് തുല്യമാകുന്നതുവരെ പ്രവർത്തിക്കുന്ന ഒരൊറ്റ ലൂപ്പ് ഞങ്ങൾ ഉപയോഗിച്ചു. അങ്ങനെ n ആവർത്തനങ്ങൾ നടത്തുന്നു, അതിനർത്ഥം നമുക്ക് രേഖീയ സമയ സങ്കീർണ്ണതയുണ്ട്.

സ്ഥല സങ്കീർണ്ണത

O (1),  ഒരു ഡിപി അറേ നിർമ്മിക്കുന്നതിനുപകരം സ്ഥിരമായ വേരിയബിളുകളുടെ എണ്ണം ഞങ്ങൾ ഉപയോഗിച്ചതിനാൽ. ഈ സമീപനം കൂടുതൽ ലാഭകരമാണ് കാരണം പ്രശ്നത്തിന്റെ പരിഹാരം അവസാന രണ്ട് ചെറിയ പ്രശ്നങ്ങളെ മാത്രം ആശ്രയിച്ചിരിക്കുന്നു.