Greedy Algorithm: Optimal Substructure I don't have a CS degree but I have recently taken up studying algorithms very seriously.
I have been studying greedy and dynamic programming for days and I come across the below definition a lot, seems they all come from the same source, but I do not understand what it means, it is one of the vaguest definitions I have ever come across. I wonder if someone can please help me explain this.
e.g. I don't understand what they mean by optimal solution, what constitutes an optimal solution, how can I define it?

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
dynamic programming and greedy algorithms for a problem
Greedy algorithms are often used when solving optimization problems, like finding the maximum or the minimum of a certain quantity, under certain conditions. Solutions that satisfy those extrema are called optimal solutions.
To answer your question, let's look at a simple example, change-making problem:

Given a set of integer values of coins $C = \{c_1, …, c_n\}$ and an amount $W$, what is the minimum number of coins to add-up to the amount $W$?

The classical greedy approach is the following:
While W &gt; 0
   pick the largest coin c that is &lt;= W
   W &lt;- W - c

For example, with $C = \{1, 2, 5\}$ and $W = 13$, you will pick $5$, $5$, $2$ and $1$, and you can show that the minimum number of coins required is indeed $4$.
However, this algorithm does not always provide an optimal solution. For example, if $C = \{1, 4, 5\}$ and $W = 8$, the greedy algorithm will choose coins $5, 1, 1, 1$ when there is a solution $4, 4$ using less coins.
Back to the topic of your question, the change-making problem does not have an optimal substructure, unless you add some hypotheses on $C$