贪心算法和动态规划：原理、区别与 C++ 示例

场景 2：面额不满足贪心性质，比如 [1,3,4]

这个例子最能说明问题。金额是 6 时，贪心会先拿 4，再补 1 和 1，得到 3 枚；但真正最优的是 3 + 3，只要 2 枚。这里就不能再靠'看起来最值'的选择了，只能老老实实上 DP。

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

// 动态规划找零：通用解法
int dpChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0;

    for (int i = 1; i <= amount; ++i) {
        for (int coin : coins) {
            if (i >= coin && dp[i - coin] != INT_MAX) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

int main() {
    vector<int> coins = {1, 3, 4};
    int amount = 6;
    int res = dpChange(coins, amount);
    if (res == -1) {
        cout << "无法凑出金额" << endl;
    } else {
        cout << "最少硬币数（DP）：' << res << endl; // 输出：2
    }
    return 0;
}

2.2 最长递增子序列（LIS）

LIS 是动态规划的经典题，不过它也有一个很有名的优化版本：贪心加二分。这个题拿来对比很合适，因为它能同时看到两种思路。

给定数组 nums，求最长严格递增子序列的长度。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 动态规划解 LIS：时间复杂度 O(n²)
int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;

    vector<int> dp(n, 1);
    int maxLen = 1;

    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        maxLen = max(maxLen, dp[i]);
    }
    return maxLen;
}

// 贪心 + 二分优化 LIS：时间复杂度 O(n log n)
int lengthOfLIS_Greedy(vector<int>& nums) {
    vector<int> tails;
    for (int num : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), num);
        if (it == tails.end()) {
            tails.push_back(num);
        } else {
            *it = num;
        }
    }
    return tails.size();
}

int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << "LIS 长度（DP）：' << lengthOfLIS(nums) << endl; // 输出：4
    cout << "LIS 长度（贪心 + 二分）：' << lengthOfLIS_Greedy(nums) << endl; // 输出：4
    return 0;
}

这里要注意，tails 并不是原序列里的真实答案，它只是帮助我们维护'长度为 k 的递增子序列，末尾元素尽量小'。这个细节很关键，不少人第一次看会误以为它就是最终序列。

2.3 活动选择问题：贪心最顺手的场景

给定多个活动的开始和结束时间，选择最多的互不重叠活动。这个题基本就是贪心的招牌例子，策略也很统一：先选结束最早的活动，给后面留出更多空间。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Activity {
    int start;
    int end;
};

// 贪心策略：选择结束时间最早的活动
int activitySelection(vector<Activity>& acts) {
    sort(acts.begin(), acts.end(), [](const Activity& a, const Activity& b) {
        return a.end < b.end;
    });

    int count = 1;
    int lastEnd = acts[0].end;

    for (int i = 1; i < acts.size(); ++i) {
        if (acts[i].start >= lastEnd) {
            count++;
            lastEnd = acts[i].end;
        }
    }
    return count;
}

int main() {
    vector<Activity> acts = {{1, 2}, {3, 4}, {0, 6}, {5, 7}, {8, 9}, {5, 9}};
    cout << "最多可选择的活动数：" << activitySelection(acts) << endl; // 输出：4
    return 0;
}

三、两种算法到底差在哪

四、实际写题时怎么选

先想贪心，通常不亏。只要能证明'现在选最优，不会影响后面'，它就很省事，代码短，跑得也快。活动选择、哈夫曼编码这类题，贪心基本就是正解。

如果局部最优和全局最优对不上，或者你发现同一个子问题会被反复算，那就别硬套贪心了，换成动态规划更稳。找零钱那种非规范面额，LIS 的基础解法，都是这么来的。

还有一种情况值得记住：有些题本质上是 DP，但可以借助贪心思路把复杂度压下来。LIS 的 O(n log n) 做法就是这个路子，思路不难，难的是先接受它'数组里存的不是答案本身'。

五、收个尾

贪心和动态规划都在解决'怎么拿到最优解'，但一个更像当下拍板，一个更像把账算完整。前者快，后者稳；前者依赖证明，后者依赖状态设计。

做题时别急着套模板。先看问题有没有贪心选择性质，再看有没有重叠子问题。能用贪心就别上 DP，贪心不成立再回到 DP，这样通常最省时间。