第 10 章 · 动态规划与贪心

子问题重叠时递归会重复计算；DP 用记忆化+递推缓存，贪心每步局部最优。

10.1 DP 两大前提

1. 最优子结构：问题的最优解包含子问题的最优解。
2. 重叠子问题：递归树里同一子问题反复出现（可用表缓存）。

自底向上递推，或用「备忘录」自顶向下——本质都是用空间换时间（第 1 章），把指数级降到多项式。

10.2 0/1 背包

容量 W 的背包，n 件物品各有重量 w[i] 和价值 v[i]，每件选或不选，求最大价值。

// dp[c]：容量 c 的最大价值；压成一维后 c 必须倒序遍历（每件只用一次）
int knapsack(int *w, int *v, int n, int W) {
    int *dp = calloc(W + 1, sizeof(int));
    if (!dp) return 0;
    for (int i = 0; i < n; i++)
        for (int c = W; c >= w[i]; c--)
            if (dp[c - w[i]] + v[i] > dp[c]) dp[c] = dp[c - w[i]] + v[i];
    int ans = dp[W];
    free(dp);
    return ans;
}

状态转移：dp[c] = max(dp[c], dp[c-w[i]] + v[i])。倒序遍历保证每件物品至多选一次。

10.3 最长公共子序列（LCS）

// dp[i][j]：X[0..i-1] 与 Y[0..j-1] 的 LCS 长度
int lcs(char *X, char *Y) {
    int n = strlen(X), m = strlen(Y);
    int (*dp)[m + 1] = calloc((n + 1) * (m + 1), sizeof(int));
    if (!dp) return 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dp[i][j] = (X[i-1] == Y[j-1])
                     ? dp[i-1][j-1] + 1
                     : (dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1]);
    int ans = dp[n][m];
    free(dp);
    return ans;
}

DP 与递归分治的区别：LCS 的两个子问题 dp[i-1][j]、dp[i][j-1] 共享 dp[i-1][j-1]，重叠，故必须记忆化。

10.4 贪心：局部最优 → 全局最优

找零：面额满足贪心条件时（如人民币 1/5/10/20/50/100），每次取不超过余额的最大面额即最优。

int change(int *coins, int n, int amt) {  // coins 已降序
    int cnt = 0;
    for (int i = 0; i < n && amt > 0; i++) {
        cnt += amt / coins[i];
        amt %= coins[i];
    }
    return amt == 0 ? cnt : -1;  // 无法凑整返回 -1
}

区间调度：按结束时间升序，每次选最早结束且不与已选冲突的区间——得到最多不重叠区间。

贪心不做回溯，一步定死；因此只有问题满足「贪心选择性质」（局部最优能推出全局最优）时才正确，否则贪心只给近似解。

对比：分治 vs DP vs 贪心——

方法	子问题	决策	典型
分治	独立、不重叠	合并子解	归并、快排
DP	重叠	记忆化 + 状态转移	背包、LCS
贪心	不回溯	每步局部最优	找零、区间调度

判断顺序：先看能否贪心（证明局部最优 → 全局最优）；不能则看子问题是否重叠——重叠用 DP，独立用分治。