6b:T4b5,// PATTERN 1: Prefix/Suffix Structure // Problem: Longest Common Subsequence of X[1..m] and Y[1..n] // // If X[m] === Y[n]: // LCS(X[1..m], Y[1..n]) = LCS(X[1..m-1], Y[1..n-1]) + 1 // Else: // LCS(X[1..m], Y[1..n]) = max(LCS(X[1..m-1], Y[1..n]), // LCS(X[1..m], Y[1..n-1])) // // Optimal substructure: If this LCS is optimal, the sub-LCS // on shorter prefixes must also be optimal. // PATTERN 2: Decision Decomposition // Problem: 0/1 Knapsack with items[1..n], capacity W // // For item n with weight w and value v: // If we INCLUDE item n: // OPT(n, W) = v + OPT(n-1, W-w) // If we EXCLUDE item n: // OPT(n, W) = OPT(n-1, W) // Take the better choice. // // Optimal substructure: Whatever decision we make about item n, // the remaining subproblem must be solved optimally. // PATTERN 3: Recursive Definition Natural // Problem: Matrix Chain Multiplication for A₁ × A₂ × ... × Aₙ // // To multiply the chain, we must choose where to split: // OPT(i, j) = min over k of { // OPT(i, k) + OPT(k+1, j) + cost(splitting at k) // } // // Optimal substructure: For the optimal split point k, // both sub-chains must be multiplied optimally.6c:T565,// Rod cutting has optimal substructure: // OPT(n) = max over i=1 to n of { price[i] + OPT(n-i) } // // Proof: // Let S be an optimal solution for rod of length n. // Let S cut off first piece of length k. // Revenue = price[k] + revenue from remaining rod of length (n-k) // // Claim: The way S handles the remaining (n-k) length must be optimal. // // Proof by contradiction: // Suppose S handles the (n-k) portion with revenue R, but // there exists a better solution for (n-k) with revenue R' > R. // Then: new total = price[k] + R' > price[k] + R = S's total // This contradicts S being optimal! // Therefore, the (n-k) portion must be handled optimally. ∎ function cutRod(prices: number[], n: number): number { // dp[i] = maximum revenue for rod of length i const dp = new Array(n + 1).fill(0); for (let length = 1; length <= n; length++) { let maxRevenue = -Infinity; // Try cutting first piece of length 1, 2, ..., length for (let firstCut = 1; firstCut <= length; firstCut++) { // Optimal substructure: dp[length - firstCut] is optimal // for the remaining length, so this combination is valid maxRevenue = Math.max( maxRevenue, prices[firstCut] + dp[length - firstCut] ); } dp[length] = maxRevenue; } return dp[n]; }6d:T56b,// LIS has optimal substructure: // LIS[i] = 1 + max{ LIS[j] : j < i AND arr[j] < arr[i] } // // The key insight: To build the longest increasing subsequence // ending at i, we extend the longest increasing subsequence // ending at some j < i (where arr[j] < arr[i]). // // This works BECAUSE of optimal substructure: we only need to // know the LENGTH of the best subsequence ending at each j, // not all possible subsequences. function lengthOfLIS(nums: number[]): number { const n = nums.length; if (n === 0) return 0; // dp[i] = length of LIS ending at index i const dp = new Array(n).fill(1); for (let i = 1; i < n; i++) { for (let j = 0; j < i; j++) { // Can we extend the LIS ending at j? if (nums[j] < nums[i]) { // Optimal substructure: dp[j] already holds the // optimal LIS length ending at j, so extending // it produces an optimal candidate for position i dp[i] = Math.max(dp[i], dp[j] + 1); } } } return Math.max(...dp); } // Why we only store LENGTH, not the actual subsequence: // Because of optimal substructure, we know that the best // subsequence of length dp[j] ending at j is as good as any // other subsequence of that length. We don't need to track // WHICH elements are in it—just that it's optimal.6e:T5a5,// The general Bellman equation pattern in DP: // // OPT[state] = optimize { cost(choice) + OPT[nextState(choice)] } // over all valid choices // // This works precisely BECAUSE of optimal substructure. // We know OPT[nextState] is the true optimal for that state, // so choosing the best immediate choice + optimal continuation // yields the global optimum. // Example: Coin Change (minimum coins to make amount) function coinChange(coins: number[], amount: number): number { // dp[x] = minimum coins to make amount x const dp = new Array(amount + 1).fill(Infinity); dp[0] = 0; // Base case: 0 coins for amount 0 for (let x = 1; x <= amount; x++) { // Bellman equation: // dp[x] = min over all coins c of { 1 + dp[x - c] } for (const coin of coins) { if (coin <= x && dp[x - coin] !== Infinity) { // THIS LINE embodies optimal substructure: // dp[x - coin] is OPTIMAL for amount (x - coin), // so adding one coin gives an OPTIMAL solution for x dp[x] = Math.min(dp[x], 1 + dp[x - coin]); } } } return dp[amount] === Infinity ? -1 : dp[amount]; } // The Bellman equation guarantees: // If we compute dp values in order from 0 to amount, // when we compute dp[x], all dp[y] for y < x are already optimal. // Thus, choosing the best coin + optimal remainder gives optimal dp[x].63:{"json":{"id":"seed_4a8608ce9b9b9fdf709b971afa7122ed","slug":"dynamic-programming-optimal-substructure","category":"Data Structures & Algorithms","topic":"Dynamic Programming","title":"Optimal Substructure — The Foundation of Dynamic Programming","description":"Master the critical mathematical property that enables dynamic programming: optimal substructure. Learn to recognize when optimal solutions must contain optimal subsolutions, how to build solutions from subproblems, and how to rigorously verify this property in any problem.","difficulty":"INTERMEDIATE","estimatedMinutes":60,"pages":[{"id":"seed_c3cac1e57df8eee38275741223bf0fa9","title":"Optimal Solution Contains Optimal Subsolutions","order":0,"content":[{"id":"opening-hook","title":"The Hidden Structure in Optimal Solutions","content":[{"data":{"content":"Imagine you're planning a road trip from New York to Los Angeles. You've calculated the absolute shortest route—the one that minimizes total driving distance across thousands of possible paths. Now, here's a profound question: **If your optimal route passes through Chicago, is the portion from New York to Chicago also the shortest possible route between those two cities?**\n\nThe answer is unequivocally *yes*. And this seemingly obvious observation contains one of the most powerful principles in all of algorithm design: **optimal substructure**.\n\nThis principle—that optimal solutions to problems must contain optimal solutions to their subproblems—is the mathematical foundation that makes dynamic programming possible. Without optimal substructure, there would be no way to build globally optimal solutions from locally optimal pieces. Without it, we'd be forced to enumerate every possible solution to find the best one."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Master","content":"By the end of this page, you will understand optimal substructure at a deep, intuitive level. You'll see why it must exist for dynamic programming to work, how to recognize it in problems, and why it represents a fundamental structural property—not a technique, but a mathematical truth about how optimal solutions are composed.","variant":"info"},"type":"callout"}]},{"id":"defining-optimal-substructure","title":"What Is Optimal Substructure?","content":[{"data":{"content":"**Optimal substructure** is a property of a problem that states:\n\n> *An optimal solution to the problem contains within it optimal solutions to subproblems.*\n\nThis definition, while precise, deserves careful unpacking because its implications are far-reaching.\n\n**Breaking down the definition:**\n\nWhen we say a problem has optimal substructure, we mean that if we take any optimal solution and decompose it into natural subparts, each subpart must itself be an optimal solution to its corresponding subproblem. There's no room for inefficiency hiding anywhere within an optimal solution."},"type":"text"},{"data":{"icon":"Lightbulb","title":"The Cut-and-Paste Intuition","content":"Here's a powerful way to understand optimal substructure: Suppose you have an optimal solution but one of its subparts is NOT optimal for its subproblem. Then you could 'cut' that suboptimal piece and 'paste' in the truly optimal piece, creating an even better overall solution. But this contradicts your assumption that you started with an optimal solution! Therefore, every piece of an optimal solution must be optimal for its corresponding subproblem.","variant":"tip"},"type":"callout"},{"data":{"content":"**Formal statement:**\n\nLet OPT(P) denote an optimal solution to problem P. Let P₁, P₂, ..., Pₖ be the subproblems that P decomposes into. Then P has optimal substructure if and only if:\n\n```\nOPT(P) = combine(OPT(P₁), OPT(P₂), ..., OPT(Pₖ))\n```\n\nIn other words, the optimal solution to the full problem can be expressed as a combination of optimal solutions to its subproblems.\n\n**What this means practically:**\n\n1. We can solve the full problem by solving smaller subproblems first\n2. We only need to find optimal solutions to subproblems—not explore all possible subsolutions\n3. The combination of optimal subsolutions yields a globally optimal solution\n4. This enables bottom-up construction of optimal solutions"},"type":"text"}],"titleType":"number","titleNumber":1},{"id":"shortest-path-example","title":"A Canonical Example: Shortest Paths","content":[{"data":{"content":"Let's establish optimal substructure through the most intuitive example: finding shortest paths in a graph.\n\n**The problem:**\nGiven a weighted graph G = (V, E) and two vertices s (source) and t (target), find the path from s to t with minimum total edge weight.\n\n**The claim:**\nIf the shortest path from s to t passes through an intermediate vertex v, then:\n- The subpath from s to v is the shortest path from s to v\n- The subpath from v to t is the shortest path from v to t"},"type":"text"},{"data":{"code":"Shortest path from A to D:\nA ----5----> B ----3----> C ----2----> D\n (total: 10)\n\nDecomposition through intermediate node B:\n┌─────────────────────┐ ┌─────────────────────┐\n│ Subproblem 1 │ │ Subproblem 2 │\n│ Shortest A → B │ + │ Shortest B → D │\n│ Answer: 5 │ │ Answer: 5 │\n└─────────────────────┘ └─────────────────────┘\n\nClaim: Both subpaths MUST be optimal.\n\nProof by contradiction:\nSuppose the A→B portion (cost 5) is NOT the shortest A→B path.\nThen there exists another path A→B with cost < 5.\nUsing this cheaper path, total A→D becomes: (<5) + 5 < 10\nBut we said 10 was the shortest A→D path! Contradiction.\nTherefore, the A→B portion MUST be the shortest A→B path. ∎","title":"Visual: Shortest Path Decomposition","language":"text"},"type":"code"},{"data":{"content":"**Why this proof matters:**\n\nThe proof by contradiction above is the template for establishing optimal substructure in any problem. It follows a consistent pattern:\n\n1. Assume you have an optimal solution to the full problem\n2. Identify a decomposition into subproblems\n3. Assume (for contradiction) that a subsolution is NOT optimal for its subproblem\n4. Show how you could improve the full solution using the truly optimal subsolution\n5. Conclude this contradicts optimality, so subsolutions must be optimal\n\nThis proof technique—often called the \"cut-and-paste\" or \"exchange\" argument—is your primary tool for verifying optimal substructure."},"type":"text"},{"data":{"icon":"Info","title":"The Power of This Property","content":"Because shortest paths have optimal substructure, we can compute the shortest path from A to D by computing shortest paths to intermediate nodes and combining them. This is exactly what Dijkstra's algorithm and Bellman-Ford exploit—they build up shortest paths incrementally, confident that optimal subsolutions combine into optimal solutions.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":2},{"id":"why-enables-dp","title":"Why Optimal Substructure Enables Dynamic Programming","content":[{"data":{"content":"Optimal substructure isn't just a nice property—it's the **mathematical justification** for dynamic programming. Without it, the entire DP approach collapses.\n\n**The core DP insight:**\n\nDynamic programming works by:\n1. Breaking a problem into subproblems\n2. Solving each unique subproblem exactly once\n3. Storing (memoizing) the optimal solution to each subproblem\n4. Combining subproblem solutions to build the final answer\n\n**Why optimal substructure is essential:**\n\nStep 4 only works if combining optimal subsolutions yields an optimal overall solution. If this weren't true—if we needed to consider *all* possible subsolutions, not just optimal ones—then memoizing only the best answer to each subproblem would be insufficient."},"type":"text"},{"data":{"rows":[["What to store for each subproblem","Only the optimal solution","All possible solutions"],["Space complexity (typically)","O(number of subproblems)","O(number of subproblems × solutions per subproblem)"],["Can build answer incrementally?","Yes—combine optimal pieces","No—must evaluate all combinations"],["Time complexity reduction","Often exponential → polynomial","No significant reduction"],["DP approach applicable?","Yes","Generally no"]],"caption":"With vs. Without Optimal Substructure","headers":["Aspect","With Optimal Substructure","Without Optimal Substructure"]},"type":"table"},{"data":{"content":"**An illuminating analogy:**\n\nConsider building a skyscraper. Optimal substructure is like the guarantee that if you build each floor to be as strong as possible for its purpose, the entire building will be as strong as possible. If this weren't true—if sometimes you needed a deliberately weaker floor to make the overall building stronger—construction would be impossibly complex.\n\nWith optimal substructure, we can focus on optimizing each subproblem independently, confident that local excellence produces global excellence."},"type":"text"},{"data":{"icon":"AlertCircle","title":"The Critical Insight","content":"Optimal substructure allows us to replace the question 'What is the optimal solution to the full problem?' with the question 'How do I combine optimal solutions to subproblems?' This reformulation is what transforms exponential brute-force into polynomial dynamic programming.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":3},{"id":"recognizing-optimal-substructure","title":"Recognizing Optimal Substructure in Problems","content":[{"data":{"content":"How do you recognize whether a problem exhibits optimal substructure? Here are the key patterns and heuristics:\n\n**Pattern 1: Prefix/Suffix Structure**\n\nMany sequence problems have optimal substructure because an optimal solution for a sequence naturally decomposes into optimal solutions for prefixes or suffixes.\n\n*Examples:* Longest increasing subsequence, edit distance, longest common subsequence\n\n**Pattern 2: Decision Decomposition**\n\nProblems where each step involves a discrete choice often have optimal substructure. After making an optimal first choice, the remaining problem must be solved optimally.\n\n*Examples:* 0/1 knapsack, rod cutting, coin change\n\n**Pattern 3: Recursive Definition Natural**\n\nIf the problem definition naturally admits a recursive formulation where the answer depends on answers to smaller instances, optimal substructure is likely present.\n\n*Examples:* Fibonacci (trivially), matrix chain multiplication, optimal BST"},"type":"text"},{"data":{"code":"$6b","title":"Pattern Recognition: Optimal Substructure Indicators","language":"typescript"},"type":"code"},{"data":{"items":["**Can you define the problem recursively in terms of smaller instances?** If yes, optimal substructure is likely.","**If you had optimal solutions to all subproblems, could you combine them to get the optimal full solution?** This is the core question.","**Does improving a subsolution improve the overall solution?** If making a subpart better always helps, you have optimal substructure.","**Can you prove via 'cut-and-paste' that suboptimal subsolutions can be improved?** This is the formal verification.","**Is the optimization goal 'decomposable' (sum, max, min)?** Additive and extremal objectives typically preserve optimal substructure."],"title":{"icon":"CheckCircle","text":"Quick Tests for Optimal Substructure","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"titleType":"number","titleNumber":4},{"id":"classic-examples","title":"Classic Examples: Seeing Optimal Substructure Clearly","content":[{"data":{"content":"Let's examine several classic problems and explicitly identify their optimal substructure property.\n\n**Example 1: Rod Cutting**\n\nGiven a rod of length n and prices p[1..n] where p[i] is the price for a rod piece of length i, find the maximum revenue obtainable by cutting the rod.\n\n*Optimal substructure:* If an optimal solution cuts off a first piece of length i, the remaining rod of length n-i must be cut optimally. If it weren't, we could cut the remaining part better and increase total revenue—contradicting optimality."},"type":"text"},{"data":{"code":"$6c","title":"Rod Cutting: Optimal Substructure Revealed","language":"typescript"},"type":"code"},{"data":{"content":"**Example 2: Longest Increasing Subsequence (LIS)**\n\nGiven a sequence X[1..n], find the longest subsequence where each element is strictly greater than the previous.\n\n*Optimal substructure:* Let LIS(i) be the length of the longest increasing subsequence ending at index i. For any j < i where X[j] < X[i], if LIS(i) includes X[j] as the second-to-last element, then the portion of that LIS ending at j must itself be a valid LIS ending at j.\n\nMore precisely: LIS(i) = 1 + max{LIS(j) : j < i and X[j] < X[i]}\n\nIf the subsolution LIS(j) weren't optimal for j, we could extend a longer increasing subsequence ending at j to reach i, contradicting LIS(i)'s optimality."},"type":"text"},{"data":{"code":"$6d","title":"LIS: Optimal Substructure in Action","language":"typescript"},"type":"code"},{"data":{"icon":"Lightbulb","title":"The Storage Reduction","content":"Notice how optimal substructure allows us to store only the optimal VALUE for each subproblem, not the entire solution structure. In LIS, we store just the length dp[j], not the actual subsequence. This compression is only valid because of optimal substructure—any optimal subsequence of that length will do.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"decomposition-choices","title":"Decomposition Choices: Not All Decompositions Work","content":[{"data":{"content":"A subtle but critical point: **the way you decompose a problem determines whether optimal substructure holds**. The same problem might have optimal substructure under one decomposition but not another.\n\n**Example: Longest Simple Path**\n\nConsider finding the longest simple path (no repeated vertices) between two vertices u and v in an unweighted graph.\n\n*Decomposition attempt:* If the longest path from u to v goes through some intermediate vertex w, is the u→w subpath the longest simple path from u to w?"},"type":"text"},{"data":{"code":"Graph:\n A ———— B\n | |\n C ———— D\n\nLongest simple path from A to D: A → B → (what's next?)\n\nLet's try: A → C → D (length 2)\nOr: A → B → D (length 2) \nOr: A → B → C → D... wait, that's length 3 but...\n\nActually, best path: A → C → B → D (length 3)\n\nNow, decompose at C:\n- Full path: A → C → B → D (length 3, the longest A→D path)\n- First part: A → C (length 1)\n\nIs A → C the longest simple path from A to C?\nNO! The longest A → C path is: A → B → D → C (length 3)\n\nBut we CAN'T use this longer A→C path in our full solution!\nIf we go A → B → D → C, we've used B and D, so we can't\ncontinue through B to reach D again.\n\nOPTIMAL SUBSTRUCTURE FAILS for longest simple path.\nThe best \"local\" choice doesn't lead to the best \"global\" solution.","title":"Longest Simple Path: Optimal Substructure Fails!","language":"text"},"type":"code"},{"data":{"content":"**Why does this fail?**\n\nThe key issue is that subproblems are **not independent**. The constraint \"simple path\" (no repeated vertices) means that the vertices used in the first subpath affect which vertices are available for the second subpath.\n\nWhen subsolutions interact—when solving one affects the constraints on another—optimal substructure can break down. The optimal first-part might use vertices needed for the optimal second-part.\n\n**Contrast with shortest paths:**\n\nFor *shortest* simple paths, optimal substructure DOES hold! Why? Because the shortest path never revisits a vertex (doing so would only add length), so there's no constraint interference between subpaths.\n\nThis illustrates a profound principle: optimal substructure depends critically on how subproblems interact."},"type":"text"},{"data":{"icon":"AlertCircle","title":"Beware of Subproblem Dependencies","content":"When subproblems share resources, constraints, or state that creates dependencies between them, optimal substructure may fail. Always verify that optimizing one subproblem doesn't prevent or degrade the optimization of another.","variant":"warning"},"type":"callout"},{"data":{"items":["**Shared resource constraints** — Subproblems compete for the same limited resources","**Path-dependent constraints** — Choices in one subproblem restrict options in another","**Non-additive objectives** — The goal isn't a simple sum/max/min of subproblem objectives","**Global constraints** — Constraints that span multiple subproblems (like 'no vertex reuse')","**Order-dependent interactions** — The order of solving subproblems affects their solutions"],"title":{"icon":"AlertTriangle","text":"Red Flags: When Optimal Substructure Might Fail","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"glass"},"type":"list"}],"titleType":"number","titleNumber":6},{"id":"mathematical-foundations","title":"Mathematical Foundations: Why It Works","content":[{"data":{"content":"Let's formalize optimal substructure mathematically to understand exactly what we're relying on.\n\n**Formal Definition:**\n\nA problem P has optimal substructure if there exists:\n1. A decomposition of any instance of P into subinstances P₁, P₂, ..., Pₖ\n2. A combination function C such that:\n - If S* is an optimal solution to P\n - And S* induces subsolutions S₁, S₂, ..., Sₖ to the subinstances\n - Then each Sᵢ is an optimal solution to Pᵢ\n - And S* = C(S₁, S₂, ..., Sₖ)\n\n**The Bellman Equation:**\n\nOptimal substructure is often expressed through the Bellman equation (or Bellman optimality equation):\n\n```\nOPT(state) = optimize_over_choices { cost(choice) + OPT(next_state(choice)) }\n```\n\nThis equation captures the essence of optimal substructure: the optimal value at any state equals the best achievable by making one choice plus the optimal value from the resulting state."},"type":"text"},{"data":{"code":"$6e","title":"The Bellman Equation in Code","language":"typescript"},"type":"code"},{"data":{"content":"**Principle of Optimality (Bellman):**\n\nRichard Bellman, who pioneered dynamic programming, stated the principle this way:\n\n> *An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision.*\n\nThis is optimal substructure in the language of decision-making. It says: once you've made a decision, you face a new state, and from that state forward, you should act optimally. The globally optimal strategy is optimal at every intermediate state.\n\n**Connection to Induction:**\n\nOptimal substructure enables proof by induction:\n- **Base case:** Trivial subproblems are solved optimally (by definition)\n- **Inductive step:** If all smaller subproblems are solved optimally, combining them optimally solves the larger problem\n- **Conclusion:** By induction, the full problem is solved optimally\n\nThis is exactly how we reason about DP correctness."},"type":"text"},{"data":{"icon":"Info","title":"The Deeper Truth","content":"Optimal substructure is not a technique—it's a mathematical property of the problem structure. When a problem has this property, DP becomes possible. When it doesn't, no amount of clever DP formulation will work. Understanding optimal substructure means understanding what makes problems 'DP-amenable.'","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":7},{"id":"summary","title":"Summary: Optimal Subsolutions Are Non-Negotiable","content":[{"data":{"content":"We've established one of the foundational truths of algorithm design: **optimal solutions contain optimal subsolutions**. This principle, called optimal substructure, is not an optional feature—it's the bedrock that makes dynamic programming mathematically valid."},"type":"text"},{"data":{"type":"ordered","items":["**Optimal substructure defined:** An optimal solution to a problem contains within it optimal solutions to its subproblems.","**Cut-and-paste proof:** If a subsolution weren't optimal, you could replace it with something better, contradicting overall optimality.","**Enables DP:** We only store optimal values for subproblems, confident that combining them yields global optima.","**Decomposition matters:** The same problem might have optimal substructure under one decomposition but not another.","**Subproblem independence:** Optimal substructure typically requires that subproblems don't interfere with each other's constraints.","**The Bellman equation:** Formalizes optimal substructure as: OPT(state) = best choice + OPT(resulting state)."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's next:**\n\nNow that we understand what optimal substructure means, we need to learn how to actually *build* optimal solutions from optimal subproblems. The next page explores the mechanics of this construction—how we combine subsolutions, handle base cases, and systematically build up to the full solution."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now understand the most fundamental property enabling dynamic programming: optimal substructure. This isn't just theory—every DP solution you ever write implicitly relies on this principle. When you write dp[i] = f(dp[j]...), you're trusting that dp[j] contains the optimal value, and that using it produces an optimal dp[i]. That trust is justified only by optimal substructure.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":8}],"isLocked":false},{"id":"seed_da39dbd3a3fff3b369acef7a83919e43","title":"Building Optimal From Optimal Subproblems","order":1,"content":null,"isLocked":true},{"id":"seed_1f8eac22b6b4833c391e63301ee6b810","title":"Connection to Greedy Optimal Substructure","order":2,"content":null,"isLocked":true},{"id":"seed_f28e8f4937e588626ac7c2517f0fc2fe","title":"Verifying Optimal Substructure","order":3,"content":null,"isLocked":true}]}}