Dynamic Programming in TheAlgorithms/Python

The 0/1 knapsack problem asks which items to include to maximize value without exceeding a weight limit. The brute-force approach checks every subset in exponential time. The DP approach recognizes that the decision for item i depends only on the best outcome for the first i-1 items, which is already in the table. If item i fits at capacity w_, the algorithm takes the maximum of two options: include the item (its value plus the best solution at the remaining capacity) or skip it (the best solution for the same capacity without this item). If the item does not fit, it is skipped and the prior row's value is copied. The table grows bottom-up from zero items to all n items, filling each cell in constant time. The answer is at dp[n][w]. For the full file including a solution-extraction function, see the deeper tour.

The LCS recurrence says: if the current characters match, the LCS of these two prefixes is one longer than the LCS of the shorter prefixes; if they do not match, take the longer of removing one character from either string. The single-line recurrence on line 65 captures all three cases in a max call. After the table is filled, dp[m][n] holds the length of the LCS. To recover the actual subsequence, the algorithm walks backward from dp[m][n]: when the diagonal value plus the match indicator equals the current cell, a matched character is prepended to seq and both indices step back; otherwise the algorithm steps toward the larger neighbor. The doctest verifies that the LCS of "programming" and "gaming" is "gaming" with length 6. For the full module, see the deeper tour.

Edit distance asks: what is the minimum number of single-character operations needed to transform one string into another? The base cases anchor the table: an empty first string requires j insertions to become a string of length j, and an empty second string requires i deletions. For matching characters, no operation is needed and the diagonal value propagates unchanged. For mismatching characters, the algorithm considers all three operations: delete a character from the first string (look up), insert a character into the first string (look left), or substitute (look diagonally). Adding 1 to the minimum of those three previous cells gives the cost for the current pair. The doctest confirms that transforming "intention" to "execution" takes 5 operations. For the top-down memoized version in the same file, see the deeper tour.

Multiplying a chain of matrices in different orders produces the same result but different numbers of scalar multiplications. For three matrices of dimensions 10x30, 30x5, and 5x20, one ordering requires 1500 + 1000 = 2500 multiplications and another requires 3000 + 6000 = 9000. The algorithm finds the optimal parenthesization without trying every possibility. It fills the matrix table by chain length: single matrices have zero cost; chains of two matrices have one split point; longer chains try every split point from a to b-1. For each split at index c, the cost is the left sub-chain cost plus the right sub-chain cost plus the cost of multiplying the two resulting matrices together. The sol table records the best split point at each interval for parenthesization reconstruction. The doctest shows that a 10x30 times 30x5 chain costs 1500 scalar multiplications.

The standard iterative LIS algorithm uses patience sorting or binary search and achieves O(n log n) time. This implementation uses recursion to expose the structure of the problem directly. The pivot is always array[0]. The function searches rightward for the first element smaller than the pivot. When found, it recurses on that suffix to get the best subsequence starting from there. It then builds a second candidate: keep the pivot and recurse on all elements that are greater than or equal to the pivot, constructing the longest non-decreasing run starting at the pivot. Whichever candidate is longer is returned. The doctests show edge cases including a decreasing array where only the last two elements form an increasing run, and a flat array where all equal elements count. The recursive structure is exponential in the worst case, making this an educational rather than production implementation.

Dijkstra finds the shortest paths from a single source. Floyd-Warshall solves a harder problem: all-pairs shortest paths in one pass. The algorithm's correctness follows from a simple recurrence: the shortest path from i to j either does not use vertex k, or it goes through k and the two sub-paths i to k and k to j are themselves shortest paths. Iterating k from 0 to n-1 considers each vertex as a potential intermediate in order, and by the time all k values have been processed, every valid intermediate has been considered for every pair. The three-line body of the loops is the entire algorithm. The doctest confirms that after adding edges 0-1 and 1-2, the shortest path from 0 to 2 is 3 (through vertex 1), while 2 to 0 remains inf because the graph is directed. Floyd-Warshall handles negative weights but not negative cycles.