Grade 11 · 10 algorithmsCitește în română

Dynamic programmingProgramare dinamică

Every dynamic programming algorithm from the Romanian high school curriculum, with the idea explained, its complexity, examples and code you can edit and run right here.

Create a free account Browse the collection

10algorithms
7chapters
1grade

Dynamic programming

Programare dinamică · 10 algorithms

Longest common subsequenceCel mai lung subșir comunTwo words a and b are given. We look for the longest sequence of letters that appears as a subsequence (letters in order, not necessarily adjacent)…O(n²)
Edit distanceDistanța de editareWhat is the minimum number of operations needed to turn the word a into the word b? An operation means inserting, deleting or replacing a letter.…O(n²)
Maximum-sum path in a matrixDrum de sumă maximă în matriceIn an n × m matrix we start from the corner (1, 1) and reach (n, m) moving only right or down. We want the maximum sum of the elements on the path.…O(n²)
Number of paths in a grid with obstaclesNumărul de drumuri într-o grilă cu obstacoleAn n × m grid has free cells (0) and obstacles (1). How many paths lead from (1, 1) to (n, m) if we move only right or down and never enter…O(n²)
Minimum number of coinsNumărul minim de monedeThere are n coin types (any number of each) and we want to pay exactly the sum S with as few coins as possible. Greedy can be wrong (for the coins…O(n²)
Number of partitions of a numberNumărul partițiilor unui numărIn how many ways can n be written as a sum of non-zero natural numbers, where the order of the terms does not matter? (4 = 4 = 3+1 = 2+2 = 2+1+1 =…O(n²)
The knapsack problem (0/1 version)Problema rucsacului (varianta discretă)A knapsack holds at most G kilograms; there are n objects with weights g[i] and values v[i], and an object is taken whole or not at all. Here greedy…O(n²)
Longest strictly increasing subsequenceSubșirul strict crescător de lungime maximăFrom a sequence of n numbers we choose a strictly increasing subsequence (elements in their order in the sequence, not necessarily adjacent) that is…O(n²)
Maximum sum in a number triangleSuma maximă în triunghiul de numereA triangle has n rows; row i holds i numbers. We start from the top and at every step go either straight down (a[i+1][j]) or down and to the right…O(n²)
Number of ways to climb a staircaseNumărul de moduri de a urca o scarăA staircase has n steps; at every move we climb either one step or two. In how many ways can we reach the top? Step i is reached either from step i…O(n)