de Prajwal M

Există multe articole de calitate despre cum să deveniți dezvoltator de software. Vă învață să programați, să dezvoltați și să utilizați biblioteci. Dar s-a făcut puțin pentru a educa Algoritmi și Structuri de date. Indiferent cât de bun ești în dezvoltare, fără să știi Algoritmi și Structuri de date, nu te poți angaja.

Învățarea algoritmilor populari precum Multiplicarea lanțului matricial, rucsac sau vânzător călător Algoritmi nu este suficient. Intervievatorii pun probleme precum cele pe care le găsiți pe site-urile de programare competitive. Pentru a rezolva astfel de probleme, trebuie să aveți o înțelegere bună și fermă a conceptelor.

Ce este programarea dinamică?

Conform Wikipedia, programarea dinamică simplifică o problemă complicată prin descompunerea ei în sub-probleme mai simple într-un recursiv manieră. Acest articol vă va învăța să:

-> Identify subproblems
-> Learn how to solve subproblems
-> Identify that subproblems are repetitive 
-> Identify that subproblems have optimal substructure property
-> Learn to cache/store results of sub problems
-> Develop a recursive relation to solve the problem
-> Use top-down and bottom-up approach to solve the problem

Ce limbă voi folosi?

Știu că majoritatea oamenilor sunt competenți sau au experiență în codificarea JavaScript. De asemenea, odată ce ați învățat în JavaScript, este foarte ușor să-l transformați în cod Java. Același lucru se poate spune despre Python sau C ++. Trucul este să înțelegeți problemele în limba care vă place cel mai mult. Prin urmare, am ales să folosesc JavaScript.

Această postare este despre algoritmi și mai concret despre programarea dinamică. În general, este perceput ca un subiect dur. Dacă ajungeți la sfârșitul postării, sunt sigur că puteți rezolva singuri multe probleme de programare dinamică ?

Declarație problemă

Problem: Given an integer n, find the minimum number of steps to reach integer 1.

At each step, you can:

Subtract 1,

Divide by 2, if it is divisible by 2

Divide by 3, if it is divisible by 3

Toate problemele de programare dinamică au starea de pornire. Datrebuie să ajungi la poartă de în tranziție printr-o numărul de stări intermediare. Într-un manual tipic, veți auzi adesea termenul subproblemă. Este la fel ca un stat. Termenii pot fi folosiți în mod interschimbabil. În acest articol, voi folosi termenul de stare în locul termenului de subproblemă.

Ce este o subproblemă sau un stat? O subproblemă / stare este o instanță mai mică a problemei inițiale. Metodele utilizate pentru a rezolva problema inițială și subproblema sunt aceleași.

Unele probleme vă vor oferi regulile care specifică tranzițiile de stat. Aceasta este o astfel de problemă. Această problemă spune că puteți trece la n-1, n / 2 sau n / 3 începând de la n. Pe de altă parte, există probleme care nu vor specifica tranzițiile de stare. Va trebui să le descoperiți singur. Voi vorbi despre aceste tipuri de probleme într-o altă postare.

Aici,

Start state -> n
Goal -> 1
Intermediate states -> any integer number between 1 and n

Având în vedere o stare (fie inițială, fie intermediară), vă puteți deplasa întotdeauna la un număr fix de stări.

from n you can move to :

n -> n-1 

if n % 2 == 0:
   n -> n/2
   
if n % 3 == 0:
   n -> n/3
   
example:

from 3 you can move to,
3 -> 3-1 = 2
3 -> 3/3 = 1

from 4 you can move to,
4 -> 4-1 = 3
4 -> 4/2 = 2

Într-o problemă de optimizare a programării dinamice, trebuie să determinați Deși vă deplasați care stări de la început la obiectiv vă va oferi o soluție optimă.

For n = 4:

approach one:
4 -> 3 -> 2 -> 1

approach two:
4 -> 2 -> 1 

approach three:
4 -> 3 -> 1

Aici, dintre cele trei abordări, abordările două și trei sunt optime, deoarece necesită cea mai mică cantitate de mișcări / tranziții. Abordarea una este cea mai rea, deoarece necesită mai multe mișcări.

Terminologiile manuale sunt explicate

Repetitive subproblems : You will end up solving the same problem more than once.

for n = 5
example:
5 -> 4 -> 3 -> 1
5 -> 4 -> 2 -> 1
5 -> 4 -> 3 -> 2 -> 1

observe here that 2 -> 1 occurs two times. 
also observe that 5 -> 4 occurs three times.

Optimal Substructure : Optimal solutions to subproblems give optimal solution to the entire problem

example:
2 -> 1 is optimal 
3 -> 1 is optimal 

when I am at 4,
4 -> 3 -> 2 -> 1 and 4 -> 3 -> 1 is possible
but the optimal solution of 4 is 4 -> 3 -> 1. The optimal solution of four comes from optimal solution of three (3 -> 1).

similarly,
4 -> 3 -> 2 -> 1 and 4 -> 2 -> 1 is possible
but the optimal solution of 4 is 4 -> 2 -> 1. The optimal solution of four comes from optimal solution of two (2 -> 1).

now 5,
The optimal solution of 5 depends on optimal solution to 4.
5 -> 4 -> 2 -> 1 and 5 -> 4 -> 3 -> 1 are optimal.

Cum ar trebui să folosiți subprobleme repetitive și substructură optimă în avantajul nostru?

Vom rezolva subproblemele o singură dată și vom rezolva fiecare subproblemă în mod optim.

we will solve the subproblems 3 -> 1 and 2 -> 1 only once and optimally.

Now for 4 we will solve only once by 4 -> 3 -> 1 and optimally. You can also solve as 4 -> 2 -> 1 but that is left to you. 

Finally for 5 we will solve only once by 5 - > 4 -> 3 -> 1 and optimally.

În practică, veți utiliza o matrice pentru a stoca rezultatul optim al unei subprobleme. În acest fel, atunci când trebuie să rezolvați din nou subproblema, puteți obține valoarea din matrice, mai degrabă decât să o rezolvați din nou. În esență, rezolvați o subproblemă o singură dată.

Cum se măsoară optimitatea

Folosind ceva numit cost. Există întotdeauna un cost asociat cu trecerea dintr-un stat în alt stat. Costul poate fi zero sau un număr finit. Setul de mișcări / tranziții care dau costul optim este soluția optimă.

In 5 -> 4 -> 3 -> 1 
for 5 -> 4 cost is 1 
for 4 -> 3 cost is 1
for 3 -> 1 cost is 1

The total cost of 5 -> 4 -> 3 -> 1 is the total sum of 3.

In In 5 -> 4 -> 3 -> 2 -> 1
for 5 -> 4 cost is 1
for 4 -> 3 cost is 1 
for 3 -> 2 cost is 1
for 2 -> 1 cost is 1
The total cost of 5 -> 3 -> 2 -> 1 is the total sum of 4.

The optimal solution of 5 -> 4 -> 3 -> 1 has a cost of three which is the minimum. Hence we can see that optimal solutions have optimal costs

Relație recursivă: Toate problemele de programare dinamică au relații recursive. Odată ce ați definit o relație recursivă, soluția o transformă doar în cod.

For the above problem, let us define minOne as the function that we will use to solve the problem and the cost of moving from one state to another as 1.

if n = 5,
solution to 5 is cost + solution to 4
recursive formulae/relation is 
minOne(5) = 1 + minOne(4) 

Similarly,
if n = 6,
recursive formulae/relation is
minOne(6) = min(             
              1 + minOne(5),
              1 + minOne(3),
              1 + minOne(2) )

Cod

Problemele de programare dinamică pot fi rezolvate printr-un de sus în jos abordare sau a de jos în sus abordare.

Top Down : Solve problems recursively. 
for n = 5, you will solve/start from 5, that is from the top of the problem.
It is a relatively easy approach provided you have a firm grasp on recursion. I say that this approach is easy as this method is as simple as transforming your recursive relation into code.

Bottom Up : Solve problems iteratively.
for n = 5, you will solve/start from 1, that is from the bottom of the problem.
This approach uses a for loop. It does not lead to stack overflow as in recursion. This approach is also slightly more optimal.

Care abordare este mai bună?

Depinde de confortul tău. Ambele oferă aceleași soluții. În probleme foarte mari, de jos în sus este benefic deoarece nu duce la depășirea stivei. Dacă alegeți o intrare de 10000, abordarea de sus în jos va depăși dimensiunea maximă a stivei de apeluri, dar o abordare de jos în sus vă va oferi soluția.

Nu uitați însă că nu puteți elimina complet gândirea recursivă. Va trebui întotdeauna să definiți o relație recursivă, indiferent de abordarea pe care o utilizați.

Abordarea de jos în sus

/*
Problem: Given an integer n, find the minimum number of steps to reach integer 1.
At each step, you can:
Subtract 1,
Divide by 2, if it is divisible by 2 
Divide by 3, if it is divisible by 2 
*/


// bottom-up
function minOneBottomUp(n) {

    const cache = [];
    // base condition
    cache[1] = 0;

    for (i = 2; i <= n; i++) {

        // initialize a , b and c to some very large numbers
        let a = 1000, b = 1000, c = 1000;

        // one step from i -> i-1
        a = 1 + cache[i - 1];

        // one step from i -> i/2 if i is divisible by 2
        if (i % 2 === 0) {
            b = 1 + cache[i / 2];
        }

        // one step from i -> i/3 if i is divisible by 3
        if (i % 3 === 0) {
            c = 1 + cache[i / 3];
        }

        // Store the minimum number of steps to reach i
        cache[i] = Math.min(a, b, c);
    }

    // return the number minimum number of steps to reach n
    return cache[n];
}

console.log(minOneBottomUp(1000));
Line 11 : The function that will solve the problem is named as minOneBottomUp. It takes n as the input.

Line 13 : The array that will be used to store results of every solved state so that there is no repeated computation is named cache. Some people like to call the array dp instead of cache. In general, cache[i] is interpreted as the minimum number of steps to reach 1 starting from i.

Line 15 : cache[1] = 0 This is the base condition. It says that minimum number of steps to reach 1 starting from 1 is 0.

Line 17 - 37 : For loop to fill up the cache with all states from 1 to n inclusive.

Line 20 : Initialize variables a, b and c to some large number. Here a represents minimum number of steps. If I did the operation n-1, b represents the minimum number of steps. If I did the operation n/2, c represents the minimum number of steps. If I did the operation n/3. The initial values of a, b and c depends upon the size of the problem.

Line 23 : a = 1 + cache[i-1]. This follows from the recursive relation we defined earlier.

Line 26 - 28: if(i % 2 == 0){
                  b = 1 + cache[i/2];
              }
              
This follows from the recursive relation we defined earlier.

Line 31 - 33: if(i % 3== 0){
                  c= 1 + cache[i/3];
              }
This follows from the recursive relation we defined earlier.

Line 36 : This the most important step.
cache[i] = Math.min(a, b, c). This essentially determines and stores which of a, b and c gave the minimum number of steps.

Line 40 : All the computations are completed. Minimum steps for all states from 1 to n is calculated. I return cache[n](minimum number of steps to reach 1 starting from n) which is the answer we wanted.

Line 43 : Testing code. It returns a value of 9

Abordare de sus în jos

/*
Problem: Given an integer n, find the minimum number of steps to reach integer 1.
At each step, you can:
Subtract 1,
Divide by 2, if it is divisible by 2 
Divide by 3, if it is divisible by 2 
*/


// top-down
function minOne(n, cache) {

    // if the array value at n is not undefined, return the value at that index
    // This is the heart of dynamic programming 
    if (typeof (cache[n]) !== 'undefined') {
        return cache[n];
    }

    // if n has reached 1 return 0
    // terminating/base condition
    if (n <= 1) {
        return 0;
    }

    // initialize a , b and c to some very large numbers
    let a = 1000, b = 1000, c = 1000;

    // one step from n -> n-1
    a = 1 + minOne(n - 1, cache);

    // one step from n -> n/2 if n is divisible by 2
    if (n % 2 === 0) {
        b = 1 + minOne(n / 2, cache);
    }

    // one step from n -> n/3 if n is divisible by 3
    if (n % 3 === 0) {
        c = 1 + minOne(n / 3, cache);
    }

    // Store the minimum number of steps to reach n 
    return cache[n] = Math.min(a, b, c);

}



const cache = [];
console.log(minOne(1000, cache));
Line 11 : The function that will solve the problem is named as minOne. It takes n and cache as the inputs.

Line 15 - 16 : It checks if for a particular state the solution has been computed or not. If it is computed it returns the previously computed value. This is the top-down way of not doing repeated computation.

Line 21 - 23 : It is the base condition. It says that if n is 1 , the minimum number of steps is 0.

Line 26 :  Initialize variables a, b and c to some large number. Here a represents minimum number of steps if I did the operation n-1, b represents the minimum number of steps if I did the operation n/2 and c represents the minimum number of steps if I did the operation n/3. The initial values of a, b and c depends upon the size of the problem.

Line 29 : a = 1 + minOne(n-1, cache). This follows from the recursive relation we defined earlier.

Line 32 - 34 : if(n % 2 == 0){
                  b = 1 + minOne(n/2, cache);
              }
This follows from the recursive relation we defined earlier.

Line 37 - 39 : if(n % 3== 0){
                  c = 1 + minOne(n/3, cache);
              }
This follows from the recursive relation we defined earlier.

Line 42 : return cache[n] = Math.min(a, b, c) . This essentially determines and stores which of a, b and c gave the minimum number of steps.

Line 48 - 49 : Testing code. It returns a value of 9

Complexitatea timpului

În problemele de programare dinamică, complexitatea timpului este numărul de stări / subprobleme * unice pentru fiecare stare.

În această problemă, pentru un n dat, există n stări / subprobleme unice. Pentru comoditate, se spune că fiecare stare este rezolvată într-un timp constant. Prin urmare, complexitatea timpului este O (n * 1).

Acest lucru poate fi verificat cu ușurință prin bucla for pe care am folosit-o în abordarea de jos în sus. Vedem că folosim doar una pentru buclă pentru a rezolva problema. Prin urmare, complexitatea timpului este O (n) sau liniar.

Aceasta este puterea programării dinamice. Permite rezolvarea eficientă a unor astfel de probleme complexe.

Complexitatea spațială

Folosim o matrice numită cache pentru a stoca rezultatele n stări. Prin urmare, dimensiunea matricei este n. Prin urmare, complexitatea spațiului este Pe).

DP ca compensare spațiu-timp

Programarea dinamică folosește spațiul pentru a rezolva mai repede o problemă. În această problemă, folosim Pe) spațiu pentru rezolvarea problemei Pe) timp. Prin urmare, schimbăm spațiu pentru viteză / timp. Prin urmare, se numește în mod adecvat Compensare spațiu-timp.

Înfășurându-se

Sper că acest post demistifică programarea dinamică. Înțeleg că citirea întregii postări ar fi putut fi dureroasă și dură, dar programarea dinamică este un subiect dificil. Stăpânirea acestuia necesită multă practică.

Voi publica mai multe articole despre demitizarea diferitelor tipuri de probleme de programare dinamică. De asemenea, voi publica un articol despre cum să transformați o soluție de backtracking într-o soluție de programare dinamică.

Dacă vă place această postare, vă rugăm să sprijiniți aplaudând? (Ați putea ajunge până la 50) și urmați-mă aici pe Medium ✌️. Vă puteți conecta cu mine pe LinkedIn . Poți să mă urmărești și mai departe Github.