Dynamic programming differs from divide-and-conquer (DnC) approaches primarily in how it deals with sub-problems. While DnC breaks a problem into independent sub-problems, dynamic programming solves interleaved sub-problems that might share smaller sub-problems. Dynamic programming employs memoization to store solutions of these overlapping sub-problems, reusing them to avoid redundant calculations, whereas DnC typically recalculates solutions for its independent sub-problems without reuse .

Memoization is critical in dynamic programming as it stores the results of solved sub-problems, enabling their reuse in solving overlapping sub-problems. This prevents redundant calculations of the same solutions and significantly improves computational efficiency by reducing the overall number of computations needed to solve the problem .

Dynamic programming solves the coin change problem by evaluating all possible ways to combine given denominations to make up the specified amount, ensuring the combination with the least number of coins is selected. This is done by storing results of solved sub-problems related to smaller amounts and building up the final solution efficiently. Unlike greedy algorithms, which may choose sub-optimal combinations by selecting the largest denomination first without full insight into future consequences, dynamic programming exhaustively checks combinations from the smallest sub-problems upward. For example, given denominations of 1, 4, 5, 15, 20, and amount 23, dynamic programming achieves the optimal solution of 15 + 4 + 4 rather than the greedy's 20 + 1 + 1 + 1 .

Defining recurrence relations is a crucial step in designing a dynamic programming solution. A recurrence relation provides a formula to express the solution of a problem in terms of solutions to smaller sub-problems. This helps to systematically break down a large problem into manageable, overlapping parts, allowing the dynamic programming algorithm to compute and store these solutions efficiently. The recurrence relations guide both the memoization process in top-down approaches and the tabulation in bottom-up approaches, ensuring that sub-problems contribute to the optimal solution of the overarching problem .

The formulation of a dynamic programming algorithm generally involves several key steps. First, characterize the optimal sub-structures and identify possible moves, akin to finding a Directed Acyclic Graph (DAG) for solution paths. Next, define the recurrence relations for the sub-problems. The solutions can then be computed recursively or iteratively in a bottom-up manner or top-down with memoization. Finally, construct an overall optimal solution or combine the solutions from sub-problems to achieve this outcome .

Dynamic programming algorithms can be implemented using a top-down approach with memoization, or a bottom-up approach. The top-down approach involves solving problems recursively and storing previously computed solutions in a cache (memoization) to avoid redundant calculations. This helps manage complex recursive calls efficiently. Alternatively, the bottom-up approach involves solving problems iteratively, which usually employs a table to store solutions of smaller sub-problems and progressively build up to the solution of the original problem. The advantage of the top-down approach is its intuitive recursive nature and manageability, while the bottom-up approach generally requires less overhead and offers faster execution since it avoids recursion and directly builds solutions from small sub-problems .

The concept of 'optimal sub-structures' in dynamic programming refers to the property that an optimal solution to a problem can be constructed efficiently from optimal solutions of its sub-problems. This principle is vital because it allows a complex problem to be broken down into simpler sub-problems that can be solved independently and then combined to form the solution to the overall problem. Recognizing these optimal sub-structures enables the formulation of recurrence relations and guides the development of dynamic programming algorithms .

Dynamic programming ensures optimal solutions to optimization problems by systematically considering and storing solutions to all possible sub-problems, thus it can evaluate all possibilities before determining the final optimal answer. In contrast, greedy algorithms make locally optimal choices at each step without considering the overall structure, which can lead to sub-optimal global solutions. For example, in the coin change problem, dynamic programming combines solutions to sub-problems for an optimal total, whereas a greedy algorithm might fail to consider the best overall combination, leading to a non-optimal solution .

The challenge in determining whether to use dynamic programming or a greedy algorithm lies in the nature of the problem. Greedy algorithms are suitable when a local optimum lead to a global optimum, which is not always the case. Problems with lots of sub-problems and overlapping sub-problems benefit from dynamic programming because it exhaustively considers all possible solutions using previous computations. Therefore, identifying the problem characteristics, such as whether optimal sub-structures and overlapping sub-problems exist, is crucial in choosing the appropriate method. Misapplying greedy methods on dynamic programming problems can result in non-optimal solutions .

Dynamic programming is often more effective than greedy algorithms for combinatorial problems because it evaluates all combinations of sub-problems to find the optimal solution. Unlike greedy algorithms, which make local optimal choices without looking at the larger picture, dynamic programming ensures that the overall combination of solutions is optimal by dynamically updating solutions based on already computed sub-problems. This is crucial in problems like the coin change problem where the optimal solution requires evaluating all possible combinations of denominations .