Hubbry Logo
Optimal substructureOptimal substructureMain
Open search
Optimal substructure
Community hub
Optimal substructure
logo
8 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Optimal substructure
Optimal substructure
Optimal substructure
View on Wikipedia
from Wikipedia
Figure 1. Finding the shortest path using optimal substructure. Numbers represent the length of the path; straight lines indicate single edges, wavy lines indicate shortest paths, i.e., there might be other vertices that are not shown here.

In computer science, a problem is said to have optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems. This property is used to determine the usefulness of greedy algorithms for a problem.[1]

Typically, a greedy algorithm is used to solve a problem with optimal substructure if it can be proven by induction that this is optimal at each step.[1] Otherwise, provided the problem exhibits overlapping subproblems as well, divide-and-conquer methods or dynamic programming may be used. If there are no appropriate greedy algorithms and the problem fails to exhibit overlapping subproblems, often a lengthy but straightforward search of the solution space is the best alternative.

In the application of dynamic programming to mathematical optimization, Richard Bellman's Principle of Optimality is based on the idea that in order to solve a dynamic optimization problem from some starting period t to some ending period T, one implicitly has to solve subproblems starting from later dates s, where t<s<T. This is an example of optimal substructure. The Principle of Optimality is used to derive the Bellman equation, which shows how the value of the problem starting from t is related to the value of the problem starting from s.

Example

[edit]

Consider finding a shortest path for traveling between two cities by car, as illustrated in Figure 1. Such an example is likely to exhibit optimal substructure. That is, if the shortest route from Seattle to Los Angeles passes through Portland and then Sacramento, then the shortest route from Portland to Los Angeles must pass through Sacramento too. That is, the problem of how to get from Portland to Los Angeles is nested inside the problem of how to get from Seattle to Los Angeles. (The wavy lines in the graph represent solutions to the subproblems.)

As an example of a problem that is unlikely to exhibit optimal substructure, consider the problem of finding the cheapest airline ticket from Buenos Aires to Moscow. Even if that ticket involves stops in Miami and then London, we can't conclude that the cheapest ticket from Miami to Moscow stops in London, because the price at which an airline sells a multi-flight trip is usually not the sum of the prices at which it would sell the individual flights in the trip.

Definition

[edit]

A slightly more formal definition of optimal substructure can be given. Let a "problem" be a collection of "alternatives", and let each alternative have an associated cost, c(a). The task is to find a set of alternatives that minimizes c(a). Suppose that the alternatives can be partitioned into subsets, i.e. each alternative belongs to only one subset. Suppose each subset has its own cost function. The minima of each of these cost functions can be found, as can the minima of the global cost function, restricted to the same subsets. If these minima match for each subset, then it's almost obvious that a global minimum can be picked not out of the full set of alternatives, but out of only the set that consists of the minima of the smaller, local cost functions we have defined. If minimizing the local functions is a problem of "lower order", and (specifically) if, after a finite number of these reductions, the problem becomes trivial, then the problem has an optimal substructure.

Problems with optimal substructure

[edit]

Problems without optimal substructure

[edit]
  • Longest path problem
  • Addition-chain exponentiation
  • Least-cost airline fare. Using online flight search, we will frequently find that the cheapest flight from airport A to airport B involves a single connection through airport C, but the cheapest flight from airport A to airport C involves a connection through some other airport D. However, if the problem takes the maximum number of layovers as a parameter, then the problem has optimal substructure. The cheapest flight from A to B that involves at most k layovers is either the direct flight; or the cheapest flight from A to some airport C that involves at most t layovers for some integer t with 0≤t<k, plus the cheapest flight from C to B that involves at most k−1−t layovers.

See also

[edit]

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Optimal substructure

View on Grokipedia
from Grokipedia
Optimal substructure is a key property of certain optimization problems, stating that an optimal solution to the problem can be constructed from optimal solutions to its subproblems. This characteristic allows complex problems to be decomposed into smaller, manageable components whose solutions combine to form the global optimum without needing to recompute overlapping parts. In the context of dynamic programming, optimal substructure is one of two essential features—the other being —that make the approach viable. It ensures that once subproblems are solved optimally, they can be reused to build larger solutions efficiently, often through bottom-up tabulation or top-down . Problems lacking this property cannot be effectively solved using dynamic programming, as combining suboptimal sub-solutions might yield a better overall result. Classic examples illustrate this property clearly. In the longest common subsequence (LCS) problem, the optimal LCS for two sequences up to indices i and j is formed by either including a matching character and taking the LCS of the prefixes, or excluding one and recursing on a subproblem—ensuring the combination yields the global optimum. Similarly, in the 0/1 , the optimal solution for a given capacity either includes the current item (using the optimal for reduced capacity and items) or excludes it (using the optimal for the remaining items), directly embodying optimal substructure. These cases demonstrate how the property facilitates proofs of correctness via cut-and-paste arguments or contradiction, confirming that sub-optimal sub-solutions cannot lead to an overall optimum.

Fundamentals

Definition

Optimal substructure is a fundamental property exhibited by certain optimization problems, where the goal is to find a solution that minimizes or maximizes an objective function among a set of feasible solutions, in contrast to decision problems that only determine whether a feasible solution exists. This property enables the recursive decomposition of the problem into smaller subproblems, ensuring that the overall optimal solution can be efficiently constructed without compromising optimality. Formally, a problem demonstrates optimal substructure if, for a given instance with solution set SS and associated subproblems with solution sets S1,S2,…,SnS_1, S_2, \dots, S_n, the optimal solution to SS, denoted \opt(S)\opt(S), satisfies \opt(S)=\combine(\opt(S1),\opt(S2),…,\opt(Sn))\opt(S) = \combine(\opt(S_1), \opt(S_2), \dots, \opt(S_n)), where \combine\combine is an efficient function that merges the subproblem solutions. This requires that the subproblem solutions themselves be optimal, rather than merely feasible, to guarantee the global solution's optimality and prevent propagation of suboptimal choices. In essence, the property allows the problem to be solved by building up from optimally solved components, a cornerstone exploited in paradigms like . Mathematically, optimal substructure is often expressed through recurrence relations that define the optimal value for a problem instance in terms of optimal values for subinstances. For example, in partitioning problems such as , it takes the form: T(n)=min⁡1≤k<n{T(k)+T(n−k)+\cost(k,n−k)}T(n) = \min_{1 \leq k < n} \left\{ T(k) + T(n - k) + \cost(k, n - k) \right\} (or using maximization where appropriate), where T(n)T(n) represents the optimal value for a problem of size nn, and \cost(k,n−k)\cost(k, n - k) captures the merging expense; this recursive structure derives from the decomposition principle inherent to the property.

Historical Background

The concept of optimal substructure emerged in the mid-20th century as a core element of dynamic programming, introduced by Richard Bellman to address complex multistage decision problems in operations research. Bellman, working at the , developed this framework during the early 1950s to model sequential optimization under uncertainty, emphasizing that an optimal policy for the overall problem must consist of optimal policies for its subproblems—a property now known as the principle of optimality, which underpins optimal substructure. This approach was motivated by practical needs in military logistics and economics, where breaking down large-scale problems into manageable recursive components allowed for efficient computation on early computers. A key milestone came with Bellman's 1957 book Dynamic Programming, which formalized the principle and provided the theoretical foundation for applying optimal substructure to a wide range of optimization challenges, including inventory control and routing. In the late 1950s and 1960s, the idea extended to graph algorithms, notably through Joseph Kruskal's 1956 work on minimum spanning trees, where the optimal solution for the full graph incorporates optimal subtrees, demonstrating the property's utility beyond pure dynamic programming. These developments highlighted optimal substructure as a unifying characteristic for problems amenable to recursive decomposition. During the 1970s and 1980s, optimal substructure integrated into broader algorithm design theory, particularly through analyses of divide-and-conquer paradigms, as explored in foundational texts like Aho, Hopcroft, and Ullman's The Design and Analysis of Computer Algorithms (1974), which connected it to efficient problem-solving strategies. By the 1990s, it gained widespread recognition in greedy algorithm contexts, with textbooks such as Cormen et al.'s Introduction to Algorithms (first edition, 1990) explicitly articulating the property as essential for verifying optimality in selection-based methods. While optimal substructure draws indirect roots from 18th-century mathematical optimization techniques, such as Joseph-Louis Lagrange's method of multipliers for constrained problems introduced in Mécanique Analytique (1788), its computational emphasis distinguishes it as a distinctly post-1950s innovation tailored to algorithmic efficiency. As of 2025, the concept remains foundational in artificial intelligence and machine learning, particularly in reinforcement learning models that rely on to propagate optimality through substructures, with ongoing applications in areas like robotics and game AI showing no fundamental paradigm shifts.

Examples and Illustrations

Basic Example

A fundamental illustration of optimal substructure is the rod-cutting problem, where a rod of length nn must be cut into integer-length pieces to maximize revenue based on given prices pip_i for each piece of length ii, with 1≤i≤n1 \leq i \leq n. The optimal revenue rnr_n for a rod of length nn satisfies the recurrence relation rn=max⁡1≤i≤n(pi+rn−i),r_n = \max_{1 \leq i \leq n} \left( p_i + r_{n-i} \right), with base case r0=0r_0 = 0. This formulation reveals the optimal substructure: the best solution for length nn is obtained by selecting the first cut of length ii that maximizes the price of that piece plus the optimal revenue for the remaining subproblem of length n−in - i. Subproblems correspond to smaller rod lengths, each of which is solved optimally and combined without overlap or redundancy in the decision process. To demonstrate, consider a rod of length 4 with prices p1=1p_1 = 1, p2=5p_2 = 5, p3=8p_3 = 8, and p4=9p_4 = 9. The optimal revenues for subproblems build incrementally:
  • For length 1: r1=p1=1r_1 = p_1 = 1.
  • For length 2: r2=max⁡(p1+r1,p2+r0)=max⁡(1+1,5+0)=5r_2 = \max(p_1 + r_1, p_2 + r_0) = \max(1 + 1, 5 + 0) = 5 (first cut of length 2).
  • For length 3: r3=max⁡(p1+r2,p2+r1,p3+r0)=max⁡(1+5,5+1,8+0)=8r_3 = \max(p_1 + r_2, p_2 + r_1, p_3 + r_0) = \max(1 + 5, 5 + 1, 8 + 0) = 8 (first cut of length 3).
  • For length 4: r4=max⁡(p1+r3,p2+r2,p3+r1,p4+r0)=max⁡(1+8,5+5,8+1,9+0)=10r_4 = \max(p_1 + r_3, p_2 + r_2, p_3 + r_1, p_4 + r_0) = \max(1 + 8, 5 + 5, 8 + 1, 9 + 0) = 10 (first cut of length 2, followed by optimal for remaining length 2).
This computation can be summarized in the following table of optimal revenues:
Length jjOptimal revenue rjr_j
00
11
25
38
410
Here, the global optimum of 10 arises from combining optimal sub-solutions, such as r4=p2+r2r_4 = p_2 + r_2 and r2=p2+r0r_2 = p_2 + r_0, directly yielding the best overall revenue without recomputing subproblems. The rod-cutting problem exhibits optimal substructure because the optimality of subproblem solutions composes seamlessly into the full solution, enabling efficient computation via dynamic programming rather than the exponential time required by brute-force enumeration of all possible cuts.

Further Examples

One prominent example of optimal substructure is the matrix chain multiplication problem, where the goal is to determine the most efficient way to parenthesize a sequence of matrices A1,A2,…,AnA_1, A_2, \dots, A_n to minimize the total cost of multiplications, given that the cost depends on the dimensions of the matrices involved. The optimal solution exhibits optimal substructure because the best parenthesization for the chain from AiA_i to AjA_j can be found by considering all possible splits at some kk (where i≤k<ji \leq k < j) and combining the optimal costs for the subchains Ai…AkA_i \dots A_k and Ak+1…AjA_{k+1} \dots A_j, plus the cost of multiplying those two results. This leads to the recurrence: opt(i,j)=min⁡i≤k<j(opt(i,k)+opt(k+1,j)+cost(i,k,j))\text{opt}(i,j) = \min_{i \leq k < j} \left( \text{opt}(i,k) + \text{opt}(k+1,j) + \text{cost}(i,k,j) \right) where cost(i,k,j)\text{cost}(i,k,j) is the scalar multiplications needed to multiply the subchain results, typically pi−1⋅pk⋅pjp_{i-1} \cdot p_k \cdot p_j for dimension array pp. For instance, with matrices of dimensions 10×20, 20×30, 30×10, the optimal split first multiplies the second and third (cost 6000), then the first with that result (cost 2000, total 8000), demonstrating how subproblem optima merge without recomputation. Another classic illustration appears in the longest common subsequence (LCS) problem for two strings X=⟨x1,x2,…,xm⟩X = \langle x_1, x_2, \dots, x_m \rangle and Y=⟨y1,y2,…,yn⟩Y = \langle y_1, y_2, \dots, y_n \rangle, where the objective is to find the longest subsequence present in both, preserving order but not necessarily contiguity. Optimal substructure holds here because the LCS of X1..mX_{1..m} and Y1..nY_{1..n} depends on smaller subproblems: if xm=ynx_m = y_n, then LCS length is 1 plus LCS of X1..m−1X_{1..m-1} and Y1..n−1Y_{1..n-1}; otherwise, it is the maximum of LCS(X1..m−1,Y1..nX_{1..m-1}, Y_{1..n}) and LCS(X1..m,Y1..n−1X_{1..m}, Y_{1..n-1}). The recurrence is: c[i,j]={c[i−1,j−1]+1if xi=yjmax⁡(c[i−1,j],c[i,j−1])otherwisec[i,j] = \begin{cases} c[i-1,j-1] + 1 & \text{if } x_i = y_j \\ \max(c[i-1,j], c[i,j-1]) & \text{otherwise} \end{cases} with base cases c[i,0]=0c[i,0] = 0 and c[0,j]=0c[0,j] = 0. For example, with X=X = "ABCBDAB" and Y=Y = "BDCAB", the LCS "BCAB" (length 4) builds incrementally from matching suffixes and prefixes in subproblems, efficiently combining their optimal lengths. To demonstrate applicability in graph problems, consider the all-pairs shortest paths computed via the Floyd-Warshall algorithm on a weighted directed graph with nn vertices, where distances may include negative weights but no negative cycles. The algorithm leverages optimal substructure by iteratively refining shortest paths allowing intermediate vertices from a set SS, starting with direct edges and adding one vertex at a time; the optimal path from ii to jj using intermediates up to kk is the minimum of the direct path or paths via kk from the subproblems up to k−1k-1. This yields the recurrence: di,jk=min⁡(di,jk−1,di,kk−1+dk,jk−1)d^k_{i,j} = \min(d^{k-1}_{i,j}, d^{k-1}_{i,k} + d^{k-1}_{k,j}) for all i,j,ki,j,k. In a simple graph with vertices A, B, C and edges A→B (2), B→C (3), A→C (6), initializing gives d[A,C]=6, but after considering B as intermediate, it updates to min(6, 2+3)=5, merging subpath optima to find the global shortest paths in O(n3)O(n^3) time.

Applications in Algorithms

Dynamic Programming Problems

Dynamic programming is applied to optimization problems that possess optimal substructure, enabling the construction of solutions to larger instances from optimal solutions to their subproblems. This approach systematically solves subproblems and stores their results to build up the overall optimum, as formalized in the principle of optimality. A classic example is the 0/1 knapsack problem, where given n items each with weight wiw_i and value viv_i, and a knapsack capacity W, the goal is to select a subset maximizing total value without exceeding W, with each item either taken or not. The problem exhibits optimal substructure: the optimal solution for the first j items and capacity x either excludes item j (reducing to the subproblem with j-1 items) or includes it (reducing to the subproblem with j-1 items and capacity x - w_j, plus v_j). The recurrence relation is: K(x,j)=max⁡(K(x,j−1), K(x−wj,j−1)+vj)K(x, j) = \max \left( K(x, j-1), \, K(x - w_j, j-1) + v_j \right) with base cases K(0,j)=0K(0, j) = 0 and K(x,0)=0K(x, 0) = 0 for all x, j; if x < w_j, the second term is not considered. This is solved using a bottom-up dynamic programming table, a 2D array of size (W+1) by (n+1), filled by iterating over capacities from 1 to W and items from 1 to n:

for x = 0 to W K[x][0] = 0 for j = 0 to n K[0][j] = 0 for x = 1 to W for j = 1 to n if w_j > x K[x][j] = K[x][j-1] else K[x][j] = max(K[x][j-1], K[x - w_j][j-1] + v_j)

for x = 0 to W K[x][0] = 0 for j = 0 to n K[0][j] = 0 for x = 1 to W for j = 1 to n if w_j > x K[x][j] = K[x][j-1] else K[x][j] = max(K[x][j-1], K[x - w_j][j-1] + v_j)

The optimal value is K[W]. This yields O(nW) time and , a pseudo-polynomial improvement over the exponential-time brute-force of 2^n subsets. Another representative problem is the (LIS), where for a of n numbers, the task is to find the longest with strictly increasing values. Optimal substructure holds: the LIS ending at position k is 1 plus the length of the longest increasing ending at some prior position j < k where the value at j is less than at k. The recurrence is: LIS(k)=1+max⁡{LIS(j)∣j<k and vj<vk}\text{LIS}(k) = 1 + \max \{ \text{LIS}(j) \mid j < k \text{ and } v_j < v_k \} or 1 if no such j exists. A bottom-up approach uses a 1D array length[1..n], initialized to 1, and iterates over the sequence:

for k = 1 to n length[k] = 1 for j = 1 to k-1 if v_j < v_k and length[j] + 1 > length[k] length[k] = length[j] + 1 max_length = max(length[1..n])

for k = 1 to n length[k] = 1 for j = 1 to k-1 if v_j < v_k and length[j] + 1 > length[k] length[k] = length[j] + 1 max_length = max(length[1..n])

This computes the LIS length in O(n^2) time, vastly more efficient than the exponential brute-force check of all 2^n subsequences. In general, dynamic programming paradigms for these problems involve either bottom-up tabulation, filling tables iteratively from base cases, or top-down , recursively computing and caching subproblem optima to avoid redundancy. The tables' entries represent optimal values for subproblems defined by parameters like remaining capacity or prefix . Optimal substructure alone allows divide-and-conquer solutions without recomputation, but when paired with —as in knapsack and LIS— further boosts efficiency by reusing identical subproblem results.

Greedy Algorithm Contexts

In greedy algorithms, optimal substructure manifests through the ability to make locally optimal choices that compose into a globally optimal solution, without the need for exhaustive exploration of alternatives. This property holds when the problem allows "safe" greedy selections, where each choice reduces the problem to a subproblem whose optimal solution, combined with the prior choices, yields the overall optimum. A key framework for this is the matroid structure, where independent sets satisfy hereditary and exchange properties, enabling the greedy algorithm to select elements by decreasing weight to maximize total value under cardinality constraints. Such structures ensure that the partial solution remains optimal for the remaining elements, avoiding suboptimal paths. The condition enabling this in greedy algorithms is the greedy choice property, often proven via "greedy stays ahead" or exchange arguments, which demonstrate that a locally can be extended to a global optimum without . For instance, in for finding a , the substructure arises because selecting the cheapest edge that connects distinct components preserves optimality for the contracted graph, as justified by the cut property: any lighter edge across a cut must be included in some optimal tree, preventing propagation of suboptimality. Similarly, in for optimal prefix codes, repeatedly merging the two lowest-frequency symbols forms a where the subproblem after merging is optimally solvable, ensuring the final code lengths minimize weighted path length. Unlike dynamic programming, which builds solutions by solving bottom-up or top-down, greedy approaches rely on tailored proofs of substructure to justify skipping exhaustive computation, often achieving linear or near-linear time for large instances. This distinction highlights greedy's efficiency in problems with strong locality, such as those in matroids. In contemporary applications as of 2025, this linkage supports scalable algorithms for large-scale data, like submodular maximization in , where greedy selections on massive datasets yield near-optimal results with sublinear complexity.

Contrasts and Limitations

Problems Lacking Optimal Substructure

The absence of optimal substructure in an optimization problem is characterized by the fact that optimal solutions to subproblems do not necessarily combine to form an optimal solution to the overall problem; instead, choices made in subproblems may need global reconsideration due to interdependencies that invalidate local optima. This contrasts with problems exhibiting the property, where subproblem solutions can be efficiently assembled without backtracking. Such absence typically arises when constraints or objectives create tight couplings between parts of the problem, preventing modular decomposition. A classic example is the traveling salesman problem (TSP), which seeks the shortest Hamiltonian cycle visiting a set of cities. An optimal tour for n-1 cities cannot generally be extended to an optimal tour for n cities by simple insertion of the additional city, as this may increase the total length beyond what a full recomputation would yield, due to the global cycle constraint requiring all edges to interconnect optimally. This interdependency means that sub-tour optima fail to compose without reevaluation. Similarly, in the exact , which aims to cover an entire universe with the minimum number of sets from a collection, an optimal cover for a partial universe may select sets that overlap inefficiently with the remaining elements, failing to contribute to the global minimum because of element-sharing constraints that demand holistic selection to minimize redundancy. The reasons for lacking optimal substructure often involve strong interdependencies among subproblems, such as cycle constraints in TSP or overlap dependencies in set cover, which prevent the principle of optimality from holding in a composable manner. These issues frequently correlate with , as the absence of efficient substructure decomposition precludes polynomial-time dynamic programming, forcing algorithms to confront the full rather than leveraging structured reuse. A modern illustration appears in discrete protein folding problems, modeled on lattices like the hydrophobic-hydrophilic (HP) model, where finding the minimum-energy conformation of a protein chain is NP-complete even in two dimensions. Here, an optimal fold for a prefix of the chain may not extend to the full sequence due to long-range interactions between distant residues, necessitating global reconfiguration to minimize energy. As of 2025, these challenges persist in , particularly for de novo protein design and kinetic , where exact remains intractable despite successes in prediction. The consequences of lacking optimal substructure are profound: exact solutions typically require exponential-time methods like brute-force or branch-and-bound, while practical approaches rely on approximations or heuristics that sacrifice guarantees for scalability. This differs from structured failures in problems with the property, where suboptimal paths can be systematically pruned; instead, it underscores the need for alternative paradigms like or metaheuristics to navigate the intractability.

Implications for Algorithm Design

The presence of optimal substructure serves as a fundamental guideline in algorithm design, prompting developers to verify this property through subproblem induction—a proof technique that assumes optimal solutions exist for subproblems and demonstrates by induction on problem size that they compose into a global optimum. If confirmed, this property indicates that dynamic programming or greedy algorithms are preferable to exhaustive search methods, as they can efficiently reuse subproblem solutions to achieve optimality without recomputation. For instance, in problems like matrix-chain multiplication, the inductive verification ensures that the optimal parenthesization incorporates optimal subchains, guiding the selection of a bottom-up or memoized recursive approach over brute-force enumeration. When optimal substructure is absent, algorithm designers must pivot to alternative paradigms such as heuristics, branch-and-bound, or approximation algorithms that exploit partial structure where full optimality cannot be guaranteed efficiently. The traveling salesman problem (TSP) exemplifies this, lacking optimal substructure for an exact polynomial-time solution, yet the achieves a 3/2-approximation for the metric TSP by combining a with a minimum-weight on odd-degree vertices, leveraging to bound the tour length relative to the optimum. This approach highlights how even incomplete substructure can inform practical approximations for NP-hard problems, trading exactness for computational feasibility. Even in problems exhibiting optimal substructure, significant trade-offs arise, particularly from the computational cost of managing large state spaces in dynamic programming, where the time and can scale exponentially with input size despite the property's presence. For example, the held-karp algorithm for TSP uses dynamic programming with optimal substructure but requires O(n^2 2^n) time due to the exponential number of subproblems, rendering it impractical for large n. To address such limitations, hybrid approaches integrating neural networks with dynamic programming have emerged by 2025, such as neural approximations of value functions to prune state spaces or guide searches, enabling scalable solutions for complex optimization in AI-driven systems. Theoretically, optimal substructure connects to classes: problems with this property and a polynomial number of admit dynamic programming solutions in , as the reusable computations yield -time algorithms. In contrast, many NP-hard problems either lack optimal substructure entirely or possess it only with an exponential state space, underscoring why exhaustive or approximate methods dominate their design. This dichotomy reinforces the vs. NP , where the absence or inefficiency of substructure often signals intractability unless =NP.

References

  1. https://courses.csail.mit.edu/6.006/spring11/lectures/lec18.pdf
  2. https://www.cs.cmu.edu/~15451-f22/lectures/lec09-dp1.pdf
  3. https://sites.math.rutgers.edu/~ajl213/CLRS/Ch15.pdf
  4. http://www.cs.toronto.edu/~milad/csc373/lectures/L9.pdf
  5. https://courses.csail.mit.edu/6.006/fall10/lectures/lecture24.pdf
  6. https://people.engr.tamu.edu/djimenez/ut/utsa/cs3343/lecture11.html
  7. https://tildesites.bowdoin.edu/~ltoma/teaching/cs231/2017spring/Lectures/dynprog.pdf
  8. https://people.ucsc.edu/~ptantalo/cse102/Spring24/Handouts/DynamicProgramming.pdf
  9. https://www.cs.princeton.edu/courses/archive/spring24/cos226/lectures/DynamicProgramming.pdf
  10. https://www.rand.org/content/dam/rand/pubs/papers/2008/P550.pdf
  11. https://pubsonline.informs.org/doi/pdf/10.1287/opre.50.1.48.17791
  12. https://www.semanticscholar.org/paper/On-the-shortest-spanning-subtree-of-a-graph-and-the-Kruskal/4f08a18f205e41c786fc80160ce8e133d50832dc
  13. https://sites.math.washington.edu/~rtr/papers/rtr147-LagrangeMultipliers.pdf
  14. https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
  15. https://web.stanford.edu/class/archive/cs/cs161/cs161.1204/Lectures/Lecture13/Lecture13-compressed.pdf
  16. https://courses.cs.duke.edu/spring18/compsci330/Notes/dynamic.pdf
  17. https://www.cs.cmu.edu/~15451-f23/lectures/lecture10-dp2.pdf
  18. https://people.engr.tamu.edu/andreas-klappenecker/csce411-s14/csce411-set5b.pdf
  19. https://stanford-cs161.github.io/winter2021/assets/files/lecture14-notes.pdf
  20. https://www.cs.ucdavis.edu/~bai/ECS122A/Notes/MST.pdf
  21. https://www.cs.unh.edu/~ruml/cs758/slides/slides-12.pdf
  22. https://student.cs.uwaterloo.ca/~cs231/resources/231slidesmod03.pdf
  23. https://arxiv.org/abs/2403.10332
  24. https://courses.csail.mit.edu/6.046/spring01/psets/ps5sol.pdf
  25. https://walkccc.me/CLRS/Chap15/15.3/
  26. https://www.cs.cornell.edu/courses/cs681/2007fa/Handouts/christofides.pdf
Add your contribution
Related Hubs
User Avatar
No comments yet.