1. 动态规划7大经典题型系统盘点刚入行那会儿我最怕面试官问动态规划DP题。直到后来刷了300道LeetCode带过20多个新人才发现动态规划其实就那几套模板。今天咱们不整虚的直接上硬货——动态规划7大必考题型附带典型例题和代码模板C语言实现都是大厂面试真题库里的常客。新手最容易犯的错是直接背题解。建议先理解每种题型的特征再动手实现代码。我带的实习生里能说清楚状态转移方程背后逻辑的最后都进了头部大厂。1.1 为什么动态规划总让人头疼动态规划难在两方面一是识别题型二是定义状态。很多教程一上来就讲最优子结构、重叠子问题反而把简单问题复杂化了。实际面试中90%的DP题都能归为以下7类线性DP最长上升子序列背包问题01背包、完全背包区间DP石子合并状态机DP买卖股票最佳时机树形DP二叉树抢劫问题数位DP数字1的个数状压DP旅行商问题2. 线性DP最基础的动态规划模型2.1 最长上升子序列LISLeetCode第300题经典例题。给定数组[10,9,2,5,3,7,101,18]最长上升子序列是[2,3,7,101]长度为4。int lengthOfLIS(int* nums, int numsSize) { int dp[numsSize]; int max_len 1; for (int i 0; i numsSize; i) { dp[i] 1; for (int j 0; j i; j) { if (nums[j] nums[i]) { dp[i] fmax(dp[i], dp[j] 1); } } max_len fmax(max_len, dp[i]); } return max_len; }关键点dp[i]表示以nums[i]结尾的LIS长度状态转移dp[i] max(dp[j]1) ∀ji且nums[j]nums[i]时间复杂度O(n²)可用二分优化到O(nlogn)2.2 最大子数组和Kadane算法LeetCode第53题经典中的经典int maxSubArray(int* nums, int numsSize) { int dp[numsSize]; dp[0] nums[0]; int max_sum dp[0]; for (int i 1; i numsSize; i) { dp[i] fmax(nums[i], dp[i-1] nums[i]); max_sum fmax(max_sum, dp[i]); } return max_sum; }实际工程中遇到类似问题如股票最大收益优先考虑这个模板。空间复杂度可优化到O(1)。3. 背包问题动态规划的试金石3.1 01背包问题LeetCode没有纯01背包题但第416题分割等和子集就是变种。给定背包容量W和物品重量wt[]、价值val[]求最大价值。int knapsack(int W, int wt[], int val[], int n) { int dp[n1][W1]; 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] dp[i-1][w]; } else { dp[i][w] fmax( dp[i-1][w], dp[i-1][w-wt[i-1]] val[i-1] ); } } } return dp[n][W]; }3.2 完全背包问题LeetCode第322题零钱兑换就是典型完全背包。与01背包的区别在于物品可以无限取用。int coinChange(int* coins, int coinsSize, int amount) { int dp[amount1]; for (int i 0; i amount; i) dp[i] amount 1; dp[0] 0; for (int i 1; i amount; i) { for (int j 0; j coinsSize; j) { if (coins[j] i) { dp[i] fmin(dp[i], dp[i - coins[j]] 1); } } } return dp[amount] amount ? -1 : dp[amount]; }背包问题调试技巧打印dp表。我习惯用这个函数void print_dp(int* dp, int rows, int cols) { for (int i 0; i rows; i) { for (int j 0; j cols; j) { printf(%2d , dp[i*cols j]); } printf(\n); } }4. 区间DP解决子数组/子串问题4.1 最长回文子串LeetCode第5题用区间DP比中心扩展更易理解char* longestPalindrome(char* s) { int n strlen(s); if (n 2) return s; int dp[n][n]; memset(dp, 0, sizeof(dp)); int start 0, max_len 1; for (int i 0; i n; i) dp[i][i] 1; for (int L 2; L n; L) { for (int i 0; i n - L 1; i) { int j i L - 1; if (s[i] s[j]) { if (L 2 || dp[i1][j-1]) { dp[i][j] 1; if (L max_len) { start i; max_len L; } } } } } char* res malloc(max_len 1); strncpy(res, s start, max_len); res[max_len] \0; return res; }4.2 石子合并问题虽然不是LeetCode原题但大厂笔试常考。N堆石子排成一列每次合并相邻两堆代价为两堆石子数之和求最小总代价。int stoneMerge(int stones[], int n) { int dp[n][n]; memset(dp, 0, sizeof(dp)); int prefix[n1]; prefix[0] 0; for (int i 0; i n; i) prefix[i1] prefix[i] stones[i]; for (int len 2; len n; len) { for (int i 0; i n - len 1; i) { int j i len - 1; dp[i][j] INT_MAX; for (int k i; k j; k) { int cost dp[i][k] dp[k1][j] prefix[j1] - prefix[i]; if (cost dp[i][j]) dp[i][j] cost; } } } return dp[0][n-1]; }5. 状态机DP处理复杂状态转移5.1 买卖股票最佳时机LeetCode第121题简单版第122题进阶版。以第122题为例无限次交易int maxProfit(int* prices, int pricesSize) { int dp[pricesSize][2]; dp[0][0] 0; // 第0天不持有 dp[0][1] -prices[0]; // 第0天持有 for (int i 1; i pricesSize; i) { dp[i][0] fmax(dp[i-1][0], dp[i-1][1] prices[i]); dp[i][1] fmax(dp[i-1][1], dp[i-1][0] - prices[i]); } return dp[pricesSize-1][0]; }5.2 打家劫舍问题LeetCode第198题典型的状态机DPint rob(int* nums, int numsSize) { if (numsSize 0) return 0; int dp[numsSize][2]; dp[0][0] 0; dp[0][1] nums[0]; for (int i 1; i numsSize; i) { dp[i][0] fmax(dp[i-1][0], dp[i-1][1]); dp[i][1] dp[i-1][0] nums[i]; } return fmax(dp[numsSize-1][0], dp[numsSize-1][1]); }状态机DP调试技巧画状态转移图。我习惯用ASCII图------- | 不持有 | ---- ------- | | 卖出 | 买入 v | ------- | | 持有 | ----- -------6. 树形DP递归与动态规划的结合6.1 二叉树抢劫问题LeetCode第337题不能抢劫相邻节点struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }; int* dfs(struct TreeNode* root) { int* res malloc(2 * sizeof(int)); if (!root) { res[0] res[1] 0; return res; } int* left dfs(root-left); int* right dfs(root-right); // res[0]: 不抢当前节点 // res[1]: 抢当前节点 res[0] fmax(left[0], left[1]) fmax(right[0], right[1]); res[1] root-val left[0] right[0]; free(left); free(right); return res; } int rob(struct TreeNode* root) { int* res dfs(root); int ans fmax(res[0], res[1]); free(res); return ans; }6.2 监控二叉树LeetCode第968题每个节点三种状态#define MIN(a,b) (((a)(b))?(a):(b)) struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }; typedef struct { int a; // 被父节点监控 int b; // 被自己监控 int c; // 被子节点监控 } Status; Status dfs(struct TreeNode* root) { if (!root) return (Status){0, 9999, 0}; Status L dfs(root-left); Status R dfs(root-right); int a MIN(L.b, L.c) MIN(R.b, R.c); int b 1 MIN(L.a, MIN(L.b, L.c)) MIN(R.a, MIN(R.b, R.c)); int c MIN(L.b R.b, MIN(L.b R.c, L.c R.b)); return (Status){a, b, c}; } int minCameraCover(struct TreeNode* root) { Status res dfs(root); return MIN(res.b, res.c); }7. 数位DP与状压DP7.1 数字1的个数数位DPLeetCode第233题统计1~n中数字1出现的次数int countDigitOne(int n) { long long digit 1; int high n / 10, cur n % 10, low 0; int res 0; while (high ! 0 || cur ! 0) { if (cur 0) res high * digit; else if (cur 1) res high * digit low 1; else res (high 1) * digit; low cur * digit; cur high % 10; high / 10; digit * 10; } return res; }7.2 旅行商问题状压DP虽然不是LeetCode原题但大厂笔试出现过。给定n个城市和距离矩阵求最短环路#define INF 0x3f3f3f3f int tsp(int graph[][n], int n) { int dp[1n][n]; memset(dp, INF, sizeof(dp)); dp[1][0] 0; // 从城市0出发 for (int mask 1; mask (1n); mask) { for (int i 0; i n; i) { if (!(mask (1i))) continue; for (int j 0; j n; j) { if (mask (1j)) continue; int new_mask mask | (1j); dp[new_mask][j] fmin(dp[new_mask][j], dp[mask][i] graph[i][j]); } } } int res INF; for (int i 1; i n; i) { res fmin(res, dp[(1n)-1][i] graph[i][0]); } return res; }8. 动态规划调试技巧8.1 常见错误排查表错误现象可能原因解决方案数组越界dp数组维度不够检查n和W的取值范围结果偏小初始化不正确检查dp[0][...]和dp[...][0]结果偏大状态转移漏条件打印中间状态检查转移逻辑超时未优化重复计算改用记忆化搜索或滚动数组8.2 性能优化技巧滚动数组将二维dp压缩为一维// 01背包滚动数组优化 int knapsack(int W, int wt[], int val[], int n) { int dp[W1]; memset(dp, 0, sizeof(dp)); for (int i 0; i n; i) { for (int w W; w wt[i]; w--) { dp[w] fmax(dp[w], dp[w - wt[i]] val[i]); } } return dp[W]; }记忆化搜索适用于树形DPint memo[10001][2]; // 假设节点数不超过10000 int dfs(struct TreeNode* root, int steal) { if (!root) return 0; if (memo[root-val][steal] ! -1) return memo[root-val][steal]; int res dfs(root-left, 0) dfs(root-right, 0); if (!steal) { res fmax(res, root-val dfs(root-left, 1) dfs(root-right, 1)); } return memo[root-val][steal] res; }预处理前缀和区间DP常用int prefix[n1]; prefix[0] 0; for (int i 0; i n; i) prefix[i1] prefix[i] nums[i]; // 计算nums[i..j]的和 int sum prefix[j1] - prefix[i];9. 大厂面试真题解析9.1 字节跳动高频题最小覆盖子串虽然是滑动窗口题但可以用区间DP思路理解char* minWindow(char* s, char* t) { int need[128] {0}; int count 0; for (int i 0; t[i]; i) { need[t[i]]; count; } int l 0, r 0, min_len INT_MAX, start 0; while (s[r]) { if (need[s[r]] 0) count--; need[s[r]]--; r; while (count 0) { if (r - l min_len) { min_len r - l; start l; } need[s[l]]; if (need[s[l]] 0) count; l; } } if (min_len INT_MAX) return ; char* res malloc(min_len 1); strncpy(res, s start, min_len); res[min_len] \0; return res; }9.2 腾讯常考题编辑距离LeetCode第72题经典二维DPint minDistance(char* word1, char* word2) { int m strlen(word1), n strlen(word2); int dp[m1][n1]; 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 { dp[i][j] 1 fmin(dp[i-1][j-1], fmin(dp[i][j-1], dp[i-1][j])); } } } return dp[m][n]; }10. 动态规划学习路线建议新手阶段2周先掌握线性DP和背包问题每天3道LeetCode简单/中等题重点理解状态转移方程进阶阶段3周攻克区间DP和状态机DP尝试用不同方法解决同一问题如递归改DP参加LeetCode周赛锻炼速度高手阶段持续研究树形DP和状压DP优化空间复杂度滚动数组模拟大厂笔试环境ACM模式我带的实习生按照这个路线3个月后动态规划正确率从30%提升到85%。关键是要坚持每天手写代码光看题解是没用的。 
长河君 · 2026/11/2 9:08:13 · 阅读 1.2k 动态规划7大经典题型与LeetCode实战解析
1. 动态规划7大经典题型系统盘点刚入行那会儿我最怕面试官问动态规划DP题。直到后来刷了300道LeetCode带过20多个新人才发现动态规划其实就那几套模板。今天咱们不整虚的直接上硬货——动态规划7大必考题型附带典型例题和代码模板C语言实现都是大厂面试真题库里的常客。新手最容易犯的错是直接背题解。建议先理解每种题型的特征再动手实现代码。我带的实习生里能说清楚状态转移方程背后逻辑的最后都进了头部大厂。1.1 为什么动态规划总让人头疼动态规划难在两方面一是识别题型二是定义状态。很多教程一上来就讲最优子结构、重叠子问题反而把简单问题复杂化了。实际面试中90%的DP题都能归为以下7类线性DP最长上升子序列背包问题01背包、完全背包区间DP石子合并状态机DP买卖股票最佳时机树形DP二叉树抢劫问题数位DP数字1的个数状压DP旅行商问题2. 线性DP最基础的动态规划模型2.1 最长上升子序列LISLeetCode第300题经典例题。给定数组[10,9,2,5,3,7,101,18]最长上升子序列是[2,3,7,101]长度为4。int lengthOfLIS(int* nums, int numsSize) { int dp[numsSize]; int max_len 1; for (int i 0; i numsSize; i) { dp[i] 1; for (int j 0; j i; j) { if (nums[j] nums[i]) { dp[i] fmax(dp[i], dp[j] 1); } } max_len fmax(max_len, dp[i]); } return max_len; }关键点dp[i]表示以nums[i]结尾的LIS长度状态转移dp[i] max(dp[j]1) ∀ji且nums[j]nums[i]时间复杂度O(n²)可用二分优化到O(nlogn)2.2 最大子数组和Kadane算法LeetCode第53题经典中的经典int maxSubArray(int* nums, int numsSize) { int dp[numsSize]; dp[0] nums[0]; int max_sum dp[0]; for (int i 1; i numsSize; i) { dp[i] fmax(nums[i], dp[i-1] nums[i]); max_sum fmax(max_sum, dp[i]); } return max_sum; }实际工程中遇到类似问题如股票最大收益优先考虑这个模板。空间复杂度可优化到O(1)。3. 背包问题动态规划的试金石3.1 01背包问题LeetCode没有纯01背包题但第416题分割等和子集就是变种。给定背包容量W和物品重量wt[]、价值val[]求最大价值。int knapsack(int W, int wt[], int val[], int n) { int dp[n1][W1]; 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] dp[i-1][w]; } else { dp[i][w] fmax( dp[i-1][w], dp[i-1][w-wt[i-1]] val[i-1] ); } } } return dp[n][W]; }3.2 完全背包问题LeetCode第322题零钱兑换就是典型完全背包。与01背包的区别在于物品可以无限取用。int coinChange(int* coins, int coinsSize, int amount) { int dp[amount1]; for (int i 0; i amount; i) dp[i] amount 1; dp[0] 0; for (int i 1; i amount; i) { for (int j 0; j coinsSize; j) { if (coins[j] i) { dp[i] fmin(dp[i], dp[i - coins[j]] 1); } } } return dp[amount] amount ? -1 : dp[amount]; }背包问题调试技巧打印dp表。我习惯用这个函数void print_dp(int* dp, int rows, int cols) { for (int i 0; i rows; i) { for (int j 0; j cols; j) { printf(%2d , dp[i*cols j]); } printf(\n); } }4. 区间DP解决子数组/子串问题4.1 最长回文子串LeetCode第5题用区间DP比中心扩展更易理解char* longestPalindrome(char* s) { int n strlen(s); if (n 2) return s; int dp[n][n]; memset(dp, 0, sizeof(dp)); int start 0, max_len 1; for (int i 0; i n; i) dp[i][i] 1; for (int L 2; L n; L) { for (int i 0; i n - L 1; i) { int j i L - 1; if (s[i] s[j]) { if (L 2 || dp[i1][j-1]) { dp[i][j] 1; if (L max_len) { start i; max_len L; } } } } } char* res malloc(max_len 1); strncpy(res, s start, max_len); res[max_len] \0; return res; }4.2 石子合并问题虽然不是LeetCode原题但大厂笔试常考。N堆石子排成一列每次合并相邻两堆代价为两堆石子数之和求最小总代价。int stoneMerge(int stones[], int n) { int dp[n][n]; memset(dp, 0, sizeof(dp)); int prefix[n1]; prefix[0] 0; for (int i 0; i n; i) prefix[i1] prefix[i] stones[i]; for (int len 2; len n; len) { for (int i 0; i n - len 1; i) { int j i len - 1; dp[i][j] INT_MAX; for (int k i; k j; k) { int cost dp[i][k] dp[k1][j] prefix[j1] - prefix[i]; if (cost dp[i][j]) dp[i][j] cost; } } } return dp[0][n-1]; }5. 状态机DP处理复杂状态转移5.1 买卖股票最佳时机LeetCode第121题简单版第122题进阶版。以第122题为例无限次交易int maxProfit(int* prices, int pricesSize) { int dp[pricesSize][2]; dp[0][0] 0; // 第0天不持有 dp[0][1] -prices[0]; // 第0天持有 for (int i 1; i pricesSize; i) { dp[i][0] fmax(dp[i-1][0], dp[i-1][1] prices[i]); dp[i][1] fmax(dp[i-1][1], dp[i-1][0] - prices[i]); } return dp[pricesSize-1][0]; }5.2 打家劫舍问题LeetCode第198题典型的状态机DPint rob(int* nums, int numsSize) { if (numsSize 0) return 0; int dp[numsSize][2]; dp[0][0] 0; dp[0][1] nums[0]; for (int i 1; i numsSize; i) { dp[i][0] fmax(dp[i-1][0], dp[i-1][1]); dp[i][1] dp[i-1][0] nums[i]; } return fmax(dp[numsSize-1][0], dp[numsSize-1][1]); }状态机DP调试技巧画状态转移图。我习惯用ASCII图------- | 不持有 | ---- ------- | | 卖出 | 买入 v | ------- | | 持有 | ----- -------6. 树形DP递归与动态规划的结合6.1 二叉树抢劫问题LeetCode第337题不能抢劫相邻节点struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }; int* dfs(struct TreeNode* root) { int* res malloc(2 * sizeof(int)); if (!root) { res[0] res[1] 0; return res; } int* left dfs(root-left); int* right dfs(root-right); // res[0]: 不抢当前节点 // res[1]: 抢当前节点 res[0] fmax(left[0], left[1]) fmax(right[0], right[1]); res[1] root-val left[0] right[0]; free(left); free(right); return res; } int rob(struct TreeNode* root) { int* res dfs(root); int ans fmax(res[0], res[1]); free(res); return ans; }6.2 监控二叉树LeetCode第968题每个节点三种状态#define MIN(a,b) (((a)(b))?(a):(b)) struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }; typedef struct { int a; // 被父节点监控 int b; // 被自己监控 int c; // 被子节点监控 } Status; Status dfs(struct TreeNode* root) { if (!root) return (Status){0, 9999, 0}; Status L dfs(root-left); Status R dfs(root-right); int a MIN(L.b, L.c) MIN(R.b, R.c); int b 1 MIN(L.a, MIN(L.b, L.c)) MIN(R.a, MIN(R.b, R.c)); int c MIN(L.b R.b, MIN(L.b R.c, L.c R.b)); return (Status){a, b, c}; } int minCameraCover(struct TreeNode* root) { Status res dfs(root); return MIN(res.b, res.c); }7. 数位DP与状压DP7.1 数字1的个数数位DPLeetCode第233题统计1~n中数字1出现的次数int countDigitOne(int n) { long long digit 1; int high n / 10, cur n % 10, low 0; int res 0; while (high ! 0 || cur ! 0) { if (cur 0) res high * digit; else if (cur 1) res high * digit low 1; else res (high 1) * digit; low cur * digit; cur high % 10; high / 10; digit * 10; } return res; }7.2 旅行商问题状压DP虽然不是LeetCode原题但大厂笔试出现过。给定n个城市和距离矩阵求最短环路#define INF 0x3f3f3f3f int tsp(int graph[][n], int n) { int dp[1n][n]; memset(dp, INF, sizeof(dp)); dp[1][0] 0; // 从城市0出发 for (int mask 1; mask (1n); mask) { for (int i 0; i n; i) { if (!(mask (1i))) continue; for (int j 0; j n; j) { if (mask (1j)) continue; int new_mask mask | (1j); dp[new_mask][j] fmin(dp[new_mask][j], dp[mask][i] graph[i][j]); } } } int res INF; for (int i 1; i n; i) { res fmin(res, dp[(1n)-1][i] graph[i][0]); } return res; }8. 动态规划调试技巧8.1 常见错误排查表错误现象可能原因解决方案数组越界dp数组维度不够检查n和W的取值范围结果偏小初始化不正确检查dp[0][...]和dp[...][0]结果偏大状态转移漏条件打印中间状态检查转移逻辑超时未优化重复计算改用记忆化搜索或滚动数组8.2 性能优化技巧滚动数组将二维dp压缩为一维// 01背包滚动数组优化 int knapsack(int W, int wt[], int val[], int n) { int dp[W1]; memset(dp, 0, sizeof(dp)); for (int i 0; i n; i) { for (int w W; w wt[i]; w--) { dp[w] fmax(dp[w], dp[w - wt[i]] val[i]); } } return dp[W]; }记忆化搜索适用于树形DPint memo[10001][2]; // 假设节点数不超过10000 int dfs(struct TreeNode* root, int steal) { if (!root) return 0; if (memo[root-val][steal] ! -1) return memo[root-val][steal]; int res dfs(root-left, 0) dfs(root-right, 0); if (!steal) { res fmax(res, root-val dfs(root-left, 1) dfs(root-right, 1)); } return memo[root-val][steal] res; }预处理前缀和区间DP常用int prefix[n1]; prefix[0] 0; for (int i 0; i n; i) prefix[i1] prefix[i] nums[i]; // 计算nums[i..j]的和 int sum prefix[j1] - prefix[i];9. 大厂面试真题解析9.1 字节跳动高频题最小覆盖子串虽然是滑动窗口题但可以用区间DP思路理解char* minWindow(char* s, char* t) { int need[128] {0}; int count 0; for (int i 0; t[i]; i) { need[t[i]]; count; } int l 0, r 0, min_len INT_MAX, start 0; while (s[r]) { if (need[s[r]] 0) count--; need[s[r]]--; r; while (count 0) { if (r - l min_len) { min_len r - l; start l; } need[s[l]]; if (need[s[l]] 0) count; l; } } if (min_len INT_MAX) return ; char* res malloc(min_len 1); strncpy(res, s start, min_len); res[min_len] \0; return res; }9.2 腾讯常考题编辑距离LeetCode第72题经典二维DPint minDistance(char* word1, char* word2) { int m strlen(word1), n strlen(word2); int dp[m1][n1]; 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 { dp[i][j] 1 fmin(dp[i-1][j-1], fmin(dp[i][j-1], dp[i-1][j])); } } } return dp[m][n]; }10. 动态规划学习路线建议新手阶段2周先掌握线性DP和背包问题每天3道LeetCode简单/中等题重点理解状态转移方程进阶阶段3周攻克区间DP和状态机DP尝试用不同方法解决同一问题如递归改DP参加LeetCode周赛锻炼速度高手阶段持续研究树形DP和状压DP优化空间复杂度滚动数组模拟大厂笔试环境ACM模式我带的实习生按照这个路线3个月后动态规划正确率从30%提升到85%。关键是要坚持每天手写代码光看题解是没用的。