When Is a Greedy Algorithm Appropriate Versus Dynamic Programming?

Use a greedy algorithm when the greedy-choice property holds and there are no overlapping sub-problems; otherwise, use dynamic programming to handle overlapping sub-problems and ensure global optimality.

Choosing between greedy algorithms and dynamic programming (DP) is a fundamental decision in algorithm design. Both techniques rely on optimal substructure, but they diverge in the additional mathematical properties required to guarantee correctness. According to the source code and explanations in the labuladong/fucking-algorithm repository, the distinction hinges on whether a locally optimal decision safely leads to a global optimum or whether you must explore multiple decision branches and cache results.

Core Differences: Optimal Substructure and Beyond

Every problem solvable by either greedy or DP must exhibit optimal substructure—meaning an optimal solution contains optimal solutions to its sub-problems. However, the two approaches require different additional properties.

The Greedy-Choice Property

A greedy algorithm demands the greedy-choice property: a locally optimal choice (the best-looking option right now) must be provably part of some globally optimal solution. The proof typically relies on an exchange argument—demonstrating that replacing an optimal solution's first choice with the greedy choice never worsens the outcome. When this property holds, you can commit to a single path without backtracking.

Overlapping Sub-Problems

Dynamic programming requires overlapping sub-problems—the same sub-problem recurs in different branches of the recursion tree. DP stores these results in a memo table or uses tabulation to avoid redundant computation. Greedy algorithms usually lack overlapping sub-problems because they never revisit a state once a decision is made.

Property	Greedy Requirement	DP Requirement
Optimal substructure	✅ Required	✅ Required
Greedy-choice property	✅ Must hold	❌ Not required
Overlapping sub-problems	❌ Usually absent	✅ Must handle

Decision Framework: When to Use Each Approach

When Greedy Algorithms Are Appropriate

Select a greedy approach when these conditions align:

• Clear ordering exists: The input can be sorted by a specific criterion (e.g., intervals by end time, tasks by deadline).
• Exchange argument applies: You can mathematically prove that the first greedy choice is always safe.
• Single-pass sufficiency: No need to explore alternative branches; one linear scan after sorting yields the answer.

In 动态规划系列/贪心算法之区间调度问题.md, the interval scheduling problem demonstrates this perfectly. The algorithm sorts intervals by end time and selects the first interval, then repeatedly chooses the next interval that starts after the previous one ends. This runs in O(N log N) time (dominated by the sort) plus O(N) for the scan, using O(1) extra space.

// From 贪心算法之区间调度问题.md
class Solution {
    public int intervalSchedule(int[][] intvs) {
        if (intvs.length == 0) return 0;
        // ① sort by end time (greedy ordering)
        Arrays.sort(intvs, (a, b) -> Integer.compare(a[1], b[1]));
        int count = 1;                     // first interval is always taken
        int x_end = intvs[0][1];           // end of the last chosen interval
        for (int[] interval : intvs) {
            int start = interval[0];
            if (start >= x_end) {          // ② choose next interval that starts after current end
                count++;
                x_end = interval[1];
            }
        }
        return count;
    }
}

When Dynamic Programming Is Required

Choose DP when:

• Overlapping sub-problems exist: The same state is reached via multiple recursion paths (e.g., different ways to split a sequence).
• Local optimality fails: The best immediate choice can lead to a sub-optimal global solution.
• Min-max or enumeration needed: You must evaluate multiple choices and keep the best result, often using a recurrence relation.

The egg drop problem in 动态规划系列/高楼扔鸡蛋问题.md exemplifies this. If you greedily drop the egg from the lowest floor, you might need N drops in the worst case. Instead, the DP formulation considers that dropping from floor mid creates two sub-problems: dp(K-1, mid-1) (egg breaks) and dp(K, N-mid) (egg survives). The recurrence selects the floor minimizing the worst-case scenario—a classic min-max strategy.

// From 高楼扔鸡蛋问题.md (simplified version)
class Solution {
    int[][] memo;
    public int superEggDrop(int K, int N) {
        memo = new int[K + 1][N + 1];
        for (int[] row : memo) Arrays.fill(row, -1);
        return dp(K, N);
    }

    int dp(int K, int N) {
        if (K == 1) return N;   // only linear scan possible
        if (N == 0) return 0;
        if (memo[K][N] != -1) return memo[K][N];

        int lo = 1, hi = N, ans = N;
        // binary-search optimisation of the DP transition (min-max)
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            int broken   = dp(K - 1, mid - 1);
            int notBroken = dp(K, N - mid);
            if (broken > notBroken) {
                hi = mid - 1;
                ans = Math.min(ans, broken + 1);
            } else {
                lo = mid + 1;
                ans = Math.min(ans, notBroken + 1);
            }
        }
        return memo[K][N] = ans;
    }
}

Why Greedy Fails on DP Problems (and Vice Versa)

Greedy algorithms fail when the greedy-choice property does not hold. In the egg drop scenario, the locally optimal choice (lowest floor) does not minimize the worst-case drops. The DP solution must explore all possible drop floors to find the true optimum, memoizing results to avoid exponential explosion.

Conversely, applying DP to interval scheduling is overkill. While you could formulate a DP recurrence:

dp[i] = max(dp[i-1], 1 + dp[lastNonOverlap(i)])

This requires O(N log N) time and O(N) space. The greedy solution achieves the same asymptotic time complexity but with simpler logic and O(1) auxiliary space. Using DP adds unnecessary state tracking when a single-pass greedy scan suffices.

Complexity and Implementation Patterns

Greedy implementations typically follow this pattern:

1. Sort input by a specific key (e.g., Arrays.sort(intvs, (a, b) -> Integer.compare(a[1], b[1]))).
2. Initialize a counter and tracking variable.
3. Single linear scan to select valid elements.

Resulting complexity: O(N log N) for the sort, or O(N) if input is pre-sorted.

DP implementations follow these patterns:

• Top-down: Recursive function with memoisation table (e.g., int[][] memo in the egg drop solution).
• Bottom-up: Iterative table filling (not shown in the egg drop example above, but common in knapsack problems).

Resulting complexity: Usually O(N·M) or O(N·M·log M), where N is the problem size and M is the number of choices per state. Space complexity is O(N·M) for the memo table.

Summary

• Greedy algorithms require the greedy-choice property and optimal substructure, but not overlapping sub-problems. They run in O(N log N) or O(N) time and use constant extra space.
• Dynamic programming requires optimal substructure and overlapping sub-problems, but not the greedy-choice property. It explores multiple decision branches and caches results, typically costing O(N·M) time and space.
• The interval scheduling problem in 动态规划系列/贪心算法之区间调度问题.md is solvable by greedy because choosing the earliest-ending interval is always safe.
• The egg drop problem in 动态规划系列/高楼扔鸡蛋问题.md requires DP because the optimal drop floor depends on worst-case analysis of two overlapping sub-problems (egg breaks vs. survives).

Frequently Asked Questions

How do I prove that a greedy algorithm will produce the optimal solution?

You must prove the greedy-choice property using an exchange argument. Show that for any optimal solution, you can replace its first choice with the greedy choice without worsening the objective value. For example, in interval scheduling, you prove that an optimal solution exists where the first interval is the one with the earliest end time.

Can every problem that uses dynamic programming also use a greedy approach?

No. DP problems lack the greedy-choice property. In the egg drop problem, always dropping from the lowest floor (a greedy choice) yields a worst-case of N drops, while the DP solution achieves approximately O(log N) drops with binary search optimization. When local choices don't guarantee global optimality, you must use DP to enumerate and compare all possibilities.

Why does dynamic programming use more memory than greedy algorithms?

DP requires a memoisation table or tabulation array to store solutions to overlapping sub-problems. In the egg drop implementation, the int[][] memo array consumes O(K·N) space to cache results of dp(K, N) calls. Greedy algorithms make irrevocable choices and never revisit states, eliminating the need for storage beyond a few tracking variables.

Is the interval scheduling problem impossible to solve with dynamic programming?

It is possible but inefficient. You could define dp[i] as the maximum number of non-overlapping intervals up to index i, using the recurrence dp[i] = max(dp[i-1], 1 + dp[lastNonOverlap(i)]). However, this requires O(N log N) time and O(N) space, whereas the greedy solution in 动态规划系列/贪心算法之区间调度问题.md achieves O(N log N) time with O(1) space and simpler code.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}