贪心算法与动态规划的区别

贪心算法（Greedy Algorithm）

一、是什么？
贪心算法是一种每步都选择当前最优解的策略，通过局部最优的累积来逼近全局最优。它不回溯，不保存历史状态，仅基于当前信息做决策。

二、解决什么问题
适用于满足贪心选择性质的问题：局部最优能直接导向全局最优。典型场景包括：

任务调度（如活动选择）
最短路径（如 Dijkstra 算法）
压缩编码（如霍夫曼编码）
最小生成树（如 Prim/Kruskal 算法）

三、应用场景

无后效性：当前决策不影响后续问题结构。
子问题独立性：局部最优解无需依赖其他子问题。
高效性要求：需快速得到可行解（不要求绝对最优）。

四、重要注意事项

❗ 不保证全局最优（需数学证明贪心策略有效）。
❗ 无法处理需要“撤销”决策的场景（如背包问题中物品取舍）。

动态规划（Dynamic Programming, DP）

一、是什么？
动态规划通过保存子问题的解避免重复计算，将复杂问题分解为相互重叠的子问题，最终整合得到全局最优解。

二、解决什么问题
适用于满足以下性质的问题：

重叠子问题（Overlapping Subproblems）：子问题被重复计算。
最优子结构（Optimal Substructure）：全局最优解包含子问题的最优解。

典型场景包括：

序列问题（如最长公共子序列）
背包问题（01背包/完全背包）
路径计数（如网格最短路径）
状态转移问题（如股票买卖问题）

三、应用场景

问题可分解为多个关联子问题。
需要精确全局最优解。
子问题的解可被缓存复用（记忆化）。

四、重要注意事项

❗ 时间和空间复杂度较高（通常 O(n²) 或 O(n³)）。
❗ 需设计状态转移方程（核心难点）。

关键区别

特性	贪心算法	动态规划
最优解保证	不保证全局最优（需证明）	保证全局最优
决策依据	当前局部最优	所有子问题的历史解
计算开销	低（O(n) 或 O(n log n)）	高（通常多项式时间）
子问题处理	独立，无重叠	重叠，需存储中间结果
回溯能力	无（单向决策）	隐含回溯（通过状态转移）
经典问题	活动选择、霍夫曼编码	背包问题、编辑距离

如何区分题目类型？

分析问题特征：
- 若问题可通过 “逐步选择当前最佳” 解决 → 贪心。
- 若问题需要 “比较所有可能组合” 或 “保存历史状态” → DP。
判断子问题性质：
- 子问题无重叠且独立 → 贪心（如活动安排）。
- 子问题重叠且需复用解 → DP（如斐波那契数列）。
尝试举反例：
- 若贪心策略在某个用例失效 → 需用 DP（如部分背包问题 vs 01背包）。
观察题目要求：
- 求可行解（非严格最优）→ 贪心。
- 求精确最优解 + 问题规模适中 → DP。

示例对比

贪心示例：活动选择问题

java

// 选择最多互不相交的活动
List<int[]> selectActivities(int[][] activities) {
    Arrays.sort(activities, (a, b) -> a[1] - b[1]); // 按结束时间排序
    List<int[]> result = new ArrayList<>();
    int lastEnd = Integer.MIN_VALUE;
    for (int[] act : activities) {
        if (act[0] >= lastEnd) { // 贪心：选结束最早的活动
            result.add(act);
            lastEnd = act[1];
        }
    }
    return result;
}

DP示例：01背包问题

java

int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[][] dp = new int[n + 1][capacity + 1]; // dp[i][j]: 前i个物品容量为j的最大价值
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= capacity; j++) {
            if (j < weights[i - 1]) 
                dp[i][j] = dp[i - 1][j]; // 放不下
            else 
                dp[i][j] = Math.max(
                    dp[i - 1][j], // 不选当前
                    dp[i - 1][j - weights[i - 1]] + values[i - 1] // 选当前
                );
        }
    }
    return dp[n][capacity];
}

总结

✅ 选贪心：问题具有贪心选择性质 + 高效性优先 + 无需精确最优解。
✅ 选动态规划：问题含重叠子问题 + 需全局最优解 + 可设计状态转移方程。
笔试中先验证贪心策略是否成立（举反例），若失败则转向动态规划。多练习经典问题（如 LeetCode 122 贪心 vs 123 DP）可提升直觉。

贪心算法与动态规划的区别 ​

贪心算法（Greedy Algorithm） ​

动态规划（Dynamic Programming, DP） ​

关键区别 ​

如何区分题目类型？ ​

示例对比 ​

贪心示例：活动选择问题 ​

DP示例：01背包问题 ​

总结 ​