Which property of dynamic programming is particularly useful for solving…

Dynamic programming relies on optimal substructure: a problem has this property when an optimal solution to the whole problem can be assembled from optimal solutions to its subproblems, and when those subproblems recur or overlap, their solutions are stored and reused rather than recomputed.

For an Optimal Binary Search Tree built over a range of keys, the minimum-cost tree is formed by picking a root for that range and then recursively forming its left and right subtrees over the sub-ranges on either side. Because each sub-range subtree must itself be the cheapest possible tree for its own keys, and different root choices repeatedly reuse the same smaller index ranges, the cost table cost[i][j] can be filled in from already-computed smaller ranges instead of being solved from scratch each time. This recursive reuse of optimal sub-solutions is exactly the relationship that lets the OBST recurrence be built.

• Greedy choice property: assumes a single locally best decision at each step can be locked in permanently without revisiting it. For OBST, the cheapest root for a given key range depends on how the search frequencies are distributed on both sides of that root, so a per-step locally best pick can still miss the globally cheapest tree.

• Divide and conquer: splits a problem into independent subproblems that are each solved once and then combined, with no need to cache results because the subproblems do not recur. OBST subproblems over overlapping key ranges recur many times across different root choices, so their results must be cached and reused rather than solved independently.

• Linear programming: expresses an optimization as a linear objective function subject to linear constraints, typically solved with methods such as the simplex algorithm. It models constrained resource-allocation problems and is not the recursive subrange-reuse mechanism that the OBST recurrence needs.

So the property that makes the Optimal Binary Search Tree recurrence work is optimal substructure.