İşarəni dəyişdirin: Rəqabətli bir proqramlaşdırma sualını həll etmək üçün dinamik proqramlaşdırma istifadə edin

Əgər mənim kimi rəqabətçi bir proqramçısınızsa, proqramın ən populyar proqramlaşdırma platformalarından biri olan CodeChef-də ilk dəfə sınadığınız zaman qəbul ediləcəyi dünyadakı ən yaxşı hisslərdən biridir.

Mən təhsil müddətində həvəsli bir proqramçı idim və Hike-də bir inkişaf etdirici olaraq işləyərkən əlaqəni itirdim. Ancaq dostum Divya Godayalın sayəsində bu yaxınlarda bu sərgüzəştli proqramlaşdırma dünyasına qayıtdım.

CodeChef May 2018 Uzun Çağırış təxminən bir saat əvvəl başa çatdı və mən bu məqaləni müsabiqədəki suallardan birini təsvir edən yazı olaraq yazmaq qərarına gəldim.

Vaxt itkisini dayandırın və işə başlayın.

Problemi həll etmək

Problemin nə tələb etdiyini daha yaxşı başa düşmək üçün bir neçə nümunəyə baxaq.

Aşağıdakı ədəd ardıcıllığını nəzərdən keçirin.

4 3 1 2

İndi sual bizi müəyyən bir əməliyyatı yerinə yetirməyə vadar edir (bəlkə də 0 dəfə, eyni qaydada qalaraq). Müəyyən bir sıra ardıcıllığını ləğv edə və yeni bir ardıcıllıqla əldə edə bilərik.

-4 3 1 2 4 -3 1 -2 4 3 -1 2 4 3 1 -2 -4 -3 1 2 və s.

Sual, yaranan ardıcıllığın aşağıdakı şərtə cavab verməli olduğunu bildirir.

Uzunluğu 1-dən çox olan hər hansı bir qismən simli elementlərin cəmi ciddi müsbətdir.

Aşağıdakı ardıcıllığın etibarlı olmadığı aydındır:

-4 3 1 2 4 -3 1 -2 4 3 1 -2 -4 -3 1 2 -4 -3 -1 -2 4 3 -1 -2

Yuxarıdakı əməliyyatı yerinə yetirməklə əldə edilə bilən yalnız 2 etibarlı alt ardıcıllığımız var. Qeyd: Bütün mümkün nəticələri yazmadıq. Bu vəziyyətdə 2 ^ n olardı 16, çünki hər nömrə üçün iki seçimimiz var. Ya onu rədd etmək, ya da etməmək.

Beləliklə, iki etibarlı ardıcıllıq belədir:

4 3 1 2

4 3 -1 2

Orijinal ardıcıllıq həmişə etibarlı ardıcıllıqlardan biri olardı, çünki içindəki bütün nömrələr müsbətdir.

İndi sifarişin minimum məbləğlə tapılmasını xahiş edirik. Baxdığımız nümunə üçün tələb olunan ardıcıllıq 4 3 -1 2 olardı.

Xəsisliklə işləyərdiniz?

Bu suala xəsis bir yanaşma olardı, əgər verilən şərtlər yerinə yetirilərkən bir sıra rədd etmək mümkündürsə, onda bu nömrəni ləğv etməliyik. Ancaq bu yanaşma həmişə düzgün nəticələr vermir. Aşağıdakı nümunəyə baxaq.

4 1 3 2

Burada bu üç etibarlı nömrələr toplusuna sahib olmaq mümkündür:

4 1 3 2 4 -1 3 2 4 1 3 -2

Həm 2, həm də 1 nömrəsini də rədd edə biləcəyi aydındır. Ancaq hər ikisi eyni vaxtda deyil. Xeyriyyətsiz bir saya laqeyd yanaşsaq - yəni bir nömrə ləğv oluna bilərsə, onda biz də laqeyd yanaşırıq - onda sonda 1 nömrəsini də ləğv edəcəyik. Sonra 2 nömrəsini bizə sub-optimal bir həll verə bilər.

Beləliklə, bu acgöz yanaşma burada işləməyəcəkdir. "Bir sıra imtina edib etməməyimiz üçün müəyyən bir seçim etməliyik və hansı seçimin optimal həll təklif etdiyini öyrənməliyik".

Dinamik proqramlaşdırma kimi qoxular.

Yaxşı köhnə dinamik proqramlaşdırma

Ən maraqlı və bəlkə də ən qorxduğu alqoritmik texnikalardan biri dinamik proqramlaşdırmadır. Bu texnika ilə bu xüsusi problemi həll edəcəyik.

Dinamik proqramlaşdırma problemlərinin ən vacib addımlarından ikisi bunlardır:

  1. Təkrarlanan əlaqəni müəyyənləşdirin.
  2. Xatırlamaq lazım olanı tapın. (yadda saxla: P)

DP-yə əsaslanan yanaşma iki əsas hissəyə bölünür.

  • Bunlardan biri son kəmiyyətin minimum məbləğini tapmaq üçün istifadə etdiyimiz əsas təkrarlanmadır. Qeyd edək ki, dinamik proqramlaşdırma birbaşa son dəsti əldə etmək üçün istifadə olunmur, yalnız son nömrələr toplusunun cəmidir. Buna görə dinamik proqramlaşdırma yanaşmamız yuxarıda verilmiş nümunə üçün cəmi 8 olaraq düzgün hesablayır. 4 + 3 + (-1) + 2 = 8.
  • Həqiqətən ehtiyac duyduğumuz, nömrələrin bəzilərinin (bəlkə də) inkar edildiyi son dəyişdirilmiş nömrələr toplusudur. Həqiqi sıra dəstini tapmaq üçün ana göstərici və izləmə anlayışından istifadə edirik.

Dinamik proqramlaşdırmaya yanaşmamız üçün rekursion əlaqəmizə gəlirik.

Rekursiv əlaqəni təsvir etməzdən əvvəl vacib bir izahat odur ki, bir nömrə ləğv edilmişsə, qonşu nömrənin heç biri mənfi ola bilməz. Yəni, iki qonşu nömrə mənfi ola bilməz, çünki bu uzunluğu mənfi olan 2 uzunluğunun alt hissəsinə səbəb olur və suala görə buna icazə verilmir.

Təkrar əlaqə üçün iki dəyişənə ehtiyacımız var. Biri, serialda olduğumuz indeks nömrəsidir, digəri isə əvvəlki nömrənin (əvvəlki nömrədən birinin solunda) rədd edildiyini və ya edilmədiyini göstərən bir Boolean dəyəridir. Beləliklə, indiki indeks i olarsa, boolean, i - 2 rəqəminin rədd edildiyini və ya olmadığını söylədi. Sonrakı abzasda bu Boolean dəyişənlərin mənası ilə tanış olacaqsınız.

O (1) -də bir sayın inkar edilə biləcəyini və ya olmamasını bilməliyik. Memo əsaslı bir həll yolu ilə bir rekursiya apardığımızdan əminik ki, sağdakı nömrələr (i + 1-dən) təkrarlanmada i indeksində olsaq, bu nöqtəyə qədər işlənməmişdir. Bu o deməkdir ki, onların hamısı hələ müsbətdir.

I indeksindəki nömrənin ləğv oluna bilməməsi seçimi sağ tərəfə (əgər varsa) və sol tərəfə (varsa) bağlıdır. Sağ tərəfi sadədir. Yalnız yoxlamalıyıq

Sayı [i]

Əgər bu belə deyilsə, bu iki dəyərin əlavə edilməsi substring üçün mənfi bir dəyəri ilə nəticələnəcəkdir (i, i + 1), əməliyyatı ləğv edir.

İndi çətin hissəsi gəlir. Görməliyik ki, i-də rəqəmi ləğv etmək mənfi cəmin bir hissəsinin solda olub-olmadığını göstərir. Təkrarlamamızda i indeksinə çatsaq, artıq nömrələri işləmişik və bəziləri rədd edilmiş ola bilər.

Tutaq ki, bu nömrələr dəsti 4 1 2 1 var və ilk 1-i ləğv etdik və indi son nömrəni (1) emal edirik.

4 -1 2 [1]

Kvadrat mötərizədəki son nömrə, işləndiyimiz rəqəmdir. Doğru tərəfə gəldikdə isə, bunları ləğv edə bilərik, çünki bunlar yoxdur. 3 indeksində (0 əsaslı indeksləşdirmə) bu 1-in rədd edilməsinin nəticənin to 0-in sol hissəsində olmasına səbəb olub olmadığını yoxlamaq lazımdır. Gördüyünüz kimi, belə bir alt quruluş yaradılmışdır.

-1 2 -1

Bu alt sətirin 0 cəmi olar və sual etibarsızdır. Rəqəmlərin alt alt xəttini rədd etdikdən sonra, son dəstdəki alt sətirlər ciddi müsbət olan bir cəmi olmalıdır. Bütün uzunluqlar> 1.

Aşağıdakı yanaşmanı birbaşa burada tətbiq edə bilmirik:

Əgər nömrə [i]

Çünki 1 <2 olsa da, son 1-i rədd etsək, yuxarıda göstərildiyi kimi etibarsız sayda dəstimiz var. Bu sadə yanaşma və ya çek burada işləmir.

Budur i - 2 sayının verilmiş indeks i üçün inkar edildiyini və ya olmamasını izah edən Boolean dəyişən. İki ssenarini nəzərdən keçirək.

  • Bəli, i - 2 indeksindəki rəqəm, göstərilən nümunədəki kimi rədd edildi. Bu vəziyyətdə, i - 2-də rəqəmi ləğv etmək, i - 1-də olan sayın azalmasına səbəb olacaqdır. Nümunədə 4 1 2 1, indeks 1-də (0 əsaslı indeksləmə) laqeydlik sayının tutumunu azaldacaq.Qalan ədədi dəyərlərə tutum kimi istinad edirik. Bu sayın azaldılmasını və ya edilməməsini yoxlayarkən nəzərə alınmalıdır.
Sayı [i]
  • I - 2 indeksindəki nömrə laqeyd edilmədiyi təqdirdə, i - 1 indeksindəki nömrə tam işlənmişdir. Sadə çek
Sayı [i]

i indeksində rəqəmi ləğv edə biləcəyimizi görmək kifayətdir.

Yuxarıda müzakirə olunan bütün fikirləri ehtiva edən təkrarlama koduna baxaq.

Hamısı yaxşıdır. Ancaq bu yalnız bir rekursdur və başlıq "Dinamik Proqramlaşdırma" oxuyur. Bu, üst-üstə düşən alt problemlərin olacağını göstərir. Hər hansı birinin olub olmadığını görmək üçün recursion ağacına baxaq.

Gördüyünüz kimi, rekursiya ağacında üst-üstə düşən alt problemlər var. Beləliklə, yaddaşlardan istifadə edə bilərik.

Yadda saxlamaq çox sadədir:

"" Bu başında gəlir. İndeksin və Boolean dəyişəninin təmsil olunduğu statusun artıq buferləşdirildiyini yoxlayırıq. ""
əgər (memo [i] [is_prev_negated]! = INF) {return memo [i] [is_prev_negated]; }
...... KOD
# Bu indeksdən minimum məbləği tutun. memo [i] [is_prev_negated] = dəq (pos, neg);
# Ana göstərici son #s ana dəstini tapmaq üçün istifadə olunur [i] [is_prev_negated] = min (pos, neg) == pos? 1: -1;

Daha əvvəl qeyd edildiyi kimi, bu recursiv yanaşma etibarlı dəyişikliklər edildikdən sonra mümkün nömrələrin minimum məbləğini qaytarır.

Ancaq sual bizi bu cür dəyişikliklər edildikdən sonra minimum məbləği verəcək son nömrəni çap etməyə çağırır. Bunu etmək üçün hər bir indeks üçün və Boolean dəyişəninin hər dəyəri üçün is_prev_negated hansı optimal hərəkətin edildiyini söyləyən üstün bir göstərici istifadə etməliyik.

Valideyn [i] [is_prev_negated] = min (pos, neg) == pos? 1: -1;

Minimum məbləğin i indeksindəki rəqəmi ləğv etməklə (mümkün olduqda!) Və ya minimum məbləği görməməzliyə vurulmağından asılı olaraq sadəcə 1 və ya -1-i saxlayırıq.

Geri izləyin

İndi orijinal problemimizin həllini tapmaq üçün geri qayıtdığımız hissə gəlir. Diqqət yetirin ki, ilk nömrəni seçmək, təkrarlamanın daha da yayılmasına səbəb olur. Birinci nömrə rədd olsaydı, ikinci nömrə müsbət olar və üçüncü nömrənin qərarı valideynlə tapıla bilər [2] [əsl]. Birinci nömrə laqeyd edilməyibsə, ikinci nömrəyə keçirik və qərarı valideyn [1] [saxta] və s. İlə tapmaq olar. Koda baxaq.

Daha yaxşı bir yanaşma

Təklif olunan məhlulun fəza mürəkkəbliyinə baxsanız, bunun ikiölçülü dinamik proqramlaşdırma həlli olduğunu görərsiniz, çünki resursun statusu iki dəyişən ilə təmsil olunur, yəni baxdığımız serialların sayını göstərən indeks i. və sonra bulanıq_prev_negated. Fəza mürəkkəbliyi və zaman mürəkkəbliyi əsas etibarilə O (n) olan O (n * 2) olardı.

Ancaq bu problemi həll etmək üçün Divya Godayal tərəfindən təklif ediləndən daha yaxşı bir yanaşma da var. Bu problem hətta bir ölçülü dinamik proqramlaşdırmaya əsaslanan bir həll yolu ilə həll edilə bilər.

Əslində, boolean dəyişən is_prev_negated, müəyyən bir rəqəmi i indeksində inkar edə biləcəyimizi və ya massivin sol tərəfinə, yəni 0 .. i-1-dən olan bütün nömrələri sağ tərəfdə olduğuna görə dəyişə biləcəyimizi qərarlaşdırmağa kömək edir. hər halda, çünki bu səhifədəki bütün nömrələr müsbətdir (recursion hələ onlara çatmadığı üçün). Beləliklə, yalnız i + 1 nömrəsini sağ tərəf üçün yoxladıq, amma i indeksinin sol tərəfi üçün is_prev_negated boolean dəyişənini istifadə etməli olduq.

Belə çıxır ki, bu Boolean dəyişənini atlaya bilərik və bir sayın ləğv oluna bilməyəcəyinə qərar vermək üçün əvvəlcədən baxacağıq. Sadəcə nə deməkdir, əgər i indeksindəsinizsə, bu elementin i + 2 elementi ilə birlikdə i + 1, i elementini udmaq qabiliyyətinə sahib olub olmadığını yoxlayın. H.

Nömrələr [i] + ədədlər [i + 2]> = ədədlər [i + 1 (SWALLOW)

Belə bir fürsət varsa, i + 1 və i + 2 elementləri hər ikisi belə bir ssenaridə mənfi ola bilmədiyi üçün i-də elementi inkar etsək birbaşa i + 3-ə atlayırıq.

Yutulma şərti yerinə yetirilməzsə və i indeksindəki rəqəmi ləğv etsək, i + 2 indeksinə keçərdik, çünki hər iki halda ardıcıl iki rəqəmi inkar etmək olmaz. Buna görə i-də olan say rədd edilsə, i + 1-dəki nömrə müsbət olmalıdır. Qaranquş çek i + 2 nömrəsinin mütləq müsbət olmağını və ya orada mübahisə edib etməməyi seçdiyimizi təyin etmək üçün istifadə olunur.

Daha yaxşı başa düşmək üçün kodu yoxlayın.

Buna görə, yalnız bir dəyişən, yəni. H. Resurs vəziyyətini təyin etmək üçün istifadə olunan indeks. Vaxt və məkan mürəkkəbliyi beləliklə əvvəlki həllin yarısına qədər azaldıla bilər.

Ümid edirəm yuxarıda təsvir edilən alqoritmin necə işlədiyini və dinamik proqramlaşdırma texnikasının bu problemə necə uyğun gəldiyini başa düşdünüz. Düşünürəm ki, bu maraqlı bir problemdir, çünki yalnız dinamik proqramlaşdırmadan istifadə etməyiniz lazım deyil, eyni zamanda optimal həll yolu tapmağınıza və sualınıza cavab almağınıza kömək edəcək ana göstərici anlayışı.