Mastering Algorithm Strategies: From Greedy to Dynamic Programming

01. Summary of Different Algorithm Strategy Characteristics

Algorithm strategies focus on problem solving, while algorithms focus on implementation.

02. Greedy Strategy

The greedy approach is simple to apply but works only for a narrow set of problems; it makes locally optimal decisions in a fixed order, hoping that these lead to a globally optimal solution.

03. Recurrence Strategy

Recurrence solves a problem step‑by‑step by exploiting inherent relationships between successive states, requiring no explicit decision making at each step and is mainly used for calculations.

04. Recursive Strategy

Recursion is commonly employed in divide‑and‑conquer and dynamic programming algorithms. It solves a large problem by breaking it into smaller sub‑problems, solving each sub‑problem recursively, and combining the results. Typical features include:

Decompose an N‑size problem into smaller instances.

Apply the same decomposition to each sub‑problem.

Base case when the problem size reaches 1.

05. Enumeration Strategy

Enumeration tries every possible solution to identify the correct one, suitable for decision‑making problems where relationships between scales are unclear and the problem cannot be easily decomposed.

06. Recursive Backtracking Strategy

Similar to enumeration, backtracking explores possible solution paths and retreats when a dead end is encountered, continuing with alternative paths.

07. Divide‑and‑Conquer Strategy

This method tackles complex problems by recursively splitting them into independent sub‑problems, solving each independently, and then merging the sub‑solutions into a final answer.

08. Dynamic Programming Strategy

Dynamic programming also uses multi‑stage decision making like greedy, but it stores intermediate results to avoid redundant computation, making it both high‑efficiency and high‑resource‑consumption. It applies when a problem cannot be cleanly divided into independent stages yet follows an optimal‑substructure principle.

09. Relationships Between Algorithm Strategies

Many strategies share underlying ideas; for example, both divide‑and‑conquer and dynamic programming rely on recursion, but they differ in how sub‑problems overlap.

10. Decomposing Problems: Divide‑and‑Conquer vs Dynamic Programming

Both approaches decompose problems, but divide‑and‑conquer’s sub‑problems are independent, whereas dynamic programming’s sub‑problems may overlap, requiring memoization.

11. Multi‑Stage Problem Solving Strategies: Greedy, Recurrence, Recursion, DP

Greedy makes a single decision at each step and passes the result forward. DP generates a set of intermediate results at each stage, reusing them later. Recurrence and recursion focus on the relationship between consecutive steps, with recurrence moving forward and recursion moving backward.

12. Exhaustive Trial and Comparison: Brute Force, Enumeration, Recursive Backtracking

When no relational information exists among data points, exhaustive enumeration (including brute force and backtracking) is used. Brute‑force is suitable for small‑scale problems. Enumeration relies on loops (e.g., solving the 8‑queen problem with nested loops). Recursive backtracking can handle arbitrary sizes (e.g., N‑queen via recursion).

13. Core Idea of Algorithm Strategies

All strategies reduce problem solving to the fundamental algorithmic tools of loops and recursion.

14. Problem Types Emphasized by Algorithm Strategies

Decision problems – solvable by recurrence or recursion.

Computation problems – solvable by recurrence or recursion.

Optimization problems – suited for greedy, divide‑and‑conquer, dynamic programming, or enumeration.

Constructive problems – addressed by greedy, divide‑and‑conquer, breadth‑first search, or depth‑first search.