د رنګ کښۍ الګوریتم


مشکل کچه سخت
په مکرر ډول دننه پوښتل کیږي کوډ نیټه فیسبوک د ګوګل Intuit JP Morgan Morgan سټنلي
پیشه متحرک برنامې LeetCode

ستونزه بیان

د پینټینګ بایګ الګوریتم ویلي دي چې تاسو ته یو پوړ درکول کیږي چې ځینې پوسټونه لري (ځینې د لرګیو ټوټې یا ځینې نور ټوټې) او ځینې رنګونه. د کښت رنګ کولو لپاره د لارو تعداد ومومئ لکه چې لږترلږه یوازې 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-1) th پوسټ باید ورته (n-2) nd پوسټ ته ورته رنګ ونه لري. دا ارزښت د F (n-2) په کارولو سره ښودل شوی. نو موږ یوې قضیې ته پام کړی چېرته چې زموږ د نهم پوسټ د وروستي پوسټ سره ورته رنګ لري. موږ باید هغه لارو ته هم پام وکړو چیرې چې اوسني پوسټ او وروستی پوسټ باید ورته رنګ ونه لري. دا ارزښت د F (n-1) په کارولو سره ښودل شوی. اوس موږ د nt پوسټ رنګ کولو لپاره (k-1) لارې لرو. پدې توګه د لارو ټول شمیره د (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

د رنګ کښۍ الګوریتم لپاره جاوا کوډ

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) ،  لکه څنګه چې موږ د DP سرنی جوړولو پرځای متغیرات ثابت شمیر کارولي. دا روش ډیر عملي دی ځکه چې د ستونزې حل یوازې په تیرو دوه کوچنیو ستونزو پورې اړه لري.