动态规划（下）：四大经典问题的实战心法

好，咱们接着聊动态规划。上一讲我们把理论基础打牢了，这一讲直接上硬菜——四个在面试和工程中高频出现的经典问题。我个人觉得，把这四个问题吃透了，动态规划就算入门了八成。

说实话，我刚开始学DP的时候，看到这些题目也是一头雾水。后来在项目中反复踩坑，才慢慢摸到门道。今天我就把那些年我踩过的坑、总结的经验，一股脑儿倒给你们。

0-1背包问题：最经典的入门题

先来个最基础的。0-1背包，说白了就是：给你一个背包，容量有限，一堆物品，每个物品要么拿要么不拿，怎么装最值钱？

我当年在做一个资源调度项目时，就遇到过类似问题。服务器资源有限，任务有不同收益，怎么分配最划算？嗯，本质上就是0-1背包。

// 0-1背包标准实现
int knapsack(int W, int wt[], int val[], int n) {
    int dp[n+1][W+1];
    memset(dp, 0, sizeof(dp));
    
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            if (wt[i-1] <= w) {
                // 装得下，比较装与不装
                dp[i][w] = max(dp[i-1][w], 
                               dp[i-1][w - wt[i-1]] + val[i-1]);
            } else {
                // 装不下，只能不装
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    return dp[n][W];
}

我曾经在面试中见过有人把0-1背包写成了完全背包，结果面试官一眼就看出来了。你想想看，如果正着遍历，dp[w]会被当前物品多次更新，相当于每个物品可以无限取用。所以记住：0-1背包，容量倒着遍历。

最长公共子序列（LCS）：字符串对比的利器

LCS解决的问题是：两个字符串，找出它们最长的公共子序列（不要求连续）。

我记得在做基因序列比对项目时，LCS就是核心算法之一。两个DNA序列，找相似片段，用的就是这玩意儿。

int longestCommonSubsequence(char * text1, char * text2) {
    int m = strlen(text1), n = strlen(text2);
    int dp[m+1][n+1];
    memset(dp, 0, sizeof(dp));
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1[i-1] == text2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = fmax(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp[m][n];
}

最长递增子序列（LIS）：排序的变种

LIS问题：给定一个数组，找最长严格递增的子序列（不要求连续）。

这题有意思。我第一次做的时候，想的是用LCS的思路——把原数组排序，然后求原数组和排序后数组的LCS。但这样有个坑：如果数组有重复元素，排序后LCS会出问题。

后来我学到一个更优雅的解法：贪心+二分。维护一个数组tails，tails[i]表示长度为i+1的递增子序列的最小末尾元素。

int lengthOfLIS(int* nums, int numsSize) {
    int tails[numsSize];
    int len = 0;
    
    for (int i = 0; i < numsSize; i++) {
        // 二分查找第一个 >= nums[i] 的位置
        int left = 0, right = len;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (tails[mid] < nums[i]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        tails[left] = nums[i];
        if (left == len) len++;
    }
    return len;
}

编辑距离：字符串相似度的度量

编辑距离（Levenshtein距离）衡量的是：把一个字符串变成另一个，最少需要多少次操作（插入、删除、替换）。

这个算法在拼写检查、DNA比对、文本相似度计算中应用极广。我做过一个代码抄袭检测系统，核心就是编辑距离。

int minDistance(char * word1, char * word2) {
    int m = strlen(word1), n = strlen(word2);
    int dp[m+1][n+1];
    
    // 初始化边界
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1[i-1] == word2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                int del = dp[i-1][j];
                int ins = dp[i][j-1];
                int rep = dp[i-1][j-1];
                dp[i][j] = 1 + fmin(del, fmin(ins, rep));
            }
        }
    }
    return dp[m][n];
}

知识体系总览

这四个问题看似不同，其实底层逻辑是相通的。我画了一张图，帮你理清它们之间的关系：

避坑指南与实战心得

讲了这么多，我总结几条实战经验：

• 先画表格，再写代码。 我每次做DP题，都会先在纸上画一个二维表格，手动填几个值，确认转移方程是对的。这招帮我避免了很多逻辑错误。
• 注意下标对应关系。 dp[i]对应的是前i个元素，还是第i个元素？搞混了边界条件全错。我习惯用dp[i][j]表示前i个和前j个，这样初始化方便。
• 空间优化要谨慎。 一维数组虽然省内存，但代码可读性差。面试时我建议先写二维的，讲清楚思路，再提优化方案。
• 测试用例要覆盖边界。 空数组、单个元素、全部相等、全部不等——这些边界情况最容易出bug。

好了，动态规划的核心问题就讲到这里。这四个问题你吃透了，DP的思维模式就建立起来了。记住：状态定义是灵魂，转移方程是骨架，边界条件是血肉。三者缺一不可。