动态规划从入门到精通：算法优化与经典问题解析

1. 动态规划入门从暴力搜索到高效解法动态规划Dynamic Programming简称DP是算法竞赛中最核心的解题方法之一也是蓝桥杯等编程竞赛的必考内容。很多初学者觉得DP难以掌握其实只要理解其本质是从暴力搜索优化而来的过程就能豁然开朗。1.1 动态规划的本质动态规划本质上是一种聪明的穷举方法。它通过以下三个关键步骤解决问题状态定义明确问题的子问题是什么状态转移找出子问题之间的关系递推式边界条件确定最简单子问题的解与直接暴力搜索相比DP通过存储中间结果避免了重复计算将指数级时间复杂度优化为多项式级别。1.2 从DFS到DP的演化路径典型的DP问题通常可以按照以下路径逐步优化暴力DFS直接枚举所有可能情况记忆化搜索存储已计算的结果避免重复计算递推式DP将递归转化为迭代自底向上计算以经典的爬楼梯问题为例假设每次可以爬1或2个台阶问爬到第n阶有多少种方法。1.2.1 暴力DFS解法int dfs(int n) { if(n 0) return 1; if(n 0) return 0; return dfs(n-1) dfs(n-2); }这种解法时间复杂度为O(2^n)当n较大时完全无法接受。1.2.2 记忆化搜索优化int memo[1000] {0}; int dfs(int n) { if(n 0) return 1; if(n 0) return 0; if(memo[n]) return memo[n]; return memo[n] dfs(n-1) dfs(n-2); }通过记忆化时间复杂度降为O(n)但仍然是递归形式。1.2.3 递推式DP解法int dp[1000] {0}; dp[0] 1; dp[1] 1; for(int i 2; i n; i) { dp[i] dp[i-1] dp[i-2]; }这才是最高效的DP实现方式同样O(n)时间复杂度但常数更小。2. 动态规划经典问题解析2.1 最大子数组和问题问题描述给定一个整数数组找出连续子数组的最大和。2.1.1 暴力解法分析最直观的做法是枚举所有可能的子数组计算它们的和并取最大值int maxSum INT_MIN; for(int i 0; i n; i) { for(int j i; j n; j) { int sum 0; for(int k i; k j; k) { sum nums[k]; } maxSum max(maxSum, sum); } }这种三重循环的解法时间复杂度为O(n^3)效率极低。2.1.2 DP状态定义定义dp[i]表示以第i个元素结尾的子数组的最大和。状态转移方程为dp[i] max(nums[i], dp[i-1] nums[i])这表示要么从当前元素重新开始要么延续前面的子数组。2.1.3 DP实现代码int maxSubArray(vectorint nums) { int n nums.size(); vectorint dp(n); dp[0] nums[0]; int maxSum dp[0]; for(int i 1; i n; i) { dp[i] max(nums[i], dp[i-1] nums[i]); maxSum max(maxSum, dp[i]); } return maxSum; }时间复杂度优化到O(n)空间复杂度O(n)。还可以进一步优化空间int maxSubArray(vectorint nums) { int maxSum nums[0]; int current nums[0]; for(int i 1; i nums.size(); i) { current max(nums[i], current nums[i]); maxSum max(maxSum, current); } return maxSum; }2.2 0-1背包问题问题描述给定n个物品每个物品有重量w[i]和价值v[i]背包容量为W求能装入的最大价值。2.2.1 暴力搜索解法int dfs(int i, int remain) { if(i n) return 0; int ans dfs(i1, remain); // 不选当前物品 if(remain w[i]) { ans max(ans, dfs(i1, remain-w[i]) v[i]); // 选当前物品 } return ans; }2.2.2 记忆化搜索优化int memo[N][W] {0}; int dfs(int i, int remain) { if(memo[i][remain]) return memo[i][remain]; if(i n) return 0; int ans dfs(i1, remain); if(remain w[i]) { ans max(ans, dfs(i1, remain-w[i]) v[i]); } return memo[i][remain] ans; }2.2.3 DP解法定义dp[i][j]表示考虑前i个物品容量为j时的最大价值。状态转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i]) if j w[i] dp[i-1][j] otherwise实现代码int knapsack(int W, vectorint w, vectorint v) { int n w.size(); vectorvectorint dp(n1, vectorint(W1, 0)); for(int i 1; i n; i) { for(int j 0; j W; j) { if(j w[i-1]) { dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i-1]] v[i-1]); } else { dp[i][j] dp[i-1][j]; } } } return dp[n][W]; }空间优化版滚动数组int knapsack(int W, vectorint w, vectorint v) { int n w.size(); vectorint dp(W1, 0); for(int i 0; i n; i) { for(int j W; j w[i]; j--) { dp[j] max(dp[j], dp[j-w[i]] v[i]); } } return dp[W]; }2.3 最长公共子序列(LCS)问题描述给定两个字符串找出它们的最长公共子序列的长度。2.3.1 DP状态定义定义dp[i][j]表示text1前i个字符和text2前j个字符的LCS长度。状态转移方程if text1[i-1] text2[j-1]: dp[i][j] dp[i-1][j-1] 1 else: dp[i][j] max(dp[i-1][j], dp[i][j-1])2.3.2 DP实现代码int longestCommonSubsequence(string text1, string text2) { int m text1.size(), n text2.size(); vectorvectorint dp(m1, vectorint(n1, 0)); 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] max(dp[i-1][j], dp[i][j-1]); } } } return dp[m][n]; }3. 动态规划解题技巧3.1 如何识别DP问题DP问题通常有以下特征问题可以分解为重叠子问题问题具有最优子结构性质需要做出系列决策通常涉及最大化或最小化某些值常见DP问题类型线性DP最长递增子序列、最大子数组和等区间DP石子合并、回文分割等树形DP树上最大独立集等状态压缩DP旅行商问题等3.2 DP解题步骤定义状态明确dp数组的含义确定转移方程找出状态之间的关系初始化边界条件确定计算顺序考虑空间优化3.3 常见错误与调试技巧数组越界特别注意边界条件初始化错误确保初始状态正确转移方程错误用简单例子验证空间不足估算数据规模顺序错误确保计算顺序正确调试技巧打印dp表格用小规模数据测试对比暴力解法的结果4. 蓝桥杯DP真题解析4.1 数字三角形问题问题描述给定一个数字三角形从顶部到底部找出路径使得数字总和最大。4.1.1 DP解法分析定义dp[i][j]表示从底部到(i,j)位置的最大路径和。状态转移方程dp[i][j] max(dp[i1][j], dp[i1][j1]) triangle[i][j]4.1.2 实现代码int minimumTotal(vectorvectorint triangle) { int n triangle.size(); vectorvectorint dp(n1, vectorint(n1, 0)); for(int i n-1; i 0; i--) { for(int j 0; j i; j) { dp[i][j] min(dp[i1][j], dp[i1][j1]) triangle[i][j]; } } return dp[0][0]; }空间优化版int minimumTotal(vectorvectorint triangle) { int n triangle.size(); vectorint dp(n1, 0); for(int i n-1; i 0; i--) { for(int j 0; j i; j) { dp[j] min(dp[j], dp[j1]) triangle[i][j]; } } return dp[0]; }4.2 石子合并问题问题描述N堆石子排成一列每次合并相邻两堆代价为两堆石子数之和求最小总代价。4.2.1 区间DP解法定义dp[i][j]表示合并第i到第j堆石子的最小代价。状态转移方程dp[i][j] min(dp[i][k] dp[k1][j] sum[i][j]) for all i ≤ k j4.2.2 实现代码int stoneGame(vectorint stones) { int n stones.size(); vectorint prefix(n1, 0); for(int i 0; i n; i) { prefix[i1] prefix[i] stones[i]; } vectorvectorint dp(n, vectorint(n, 0)); for(int len 2; len n; len) { for(int i 0; i len - 1 n; i) { int j i len - 1; dp[i][j] INT_MAX; for(int k i; k j; k) { dp[i][j] min(dp[i][j], dp[i][k] dp[k1][j] prefix[j1] - prefix[i]); } } } return dp[0][n-1]; }5. 动态规划进阶技巧5.1 状态压缩DP当状态可以用位表示时可以用整数代替数组大幅节省空间。5.1.1 旅行商问题问题描述给定一系列城市和距离找出访问每个城市一次并返回起点的最短路径。状态定义dp[mask][i]表示已经访问过mask表示的城市当前在i城市的最短路径。int tsp(vectorvectorint dist) { int n dist.size(); int final_state (1 n) - 1; vectorvectorint dp(1 n, vectorint(n, INT_MAX)); // 初始化从0出发到其他城市 for(int i 0; i n; i) { dp[1 i][i] dist[0][i]; } for(int mask 0; mask (1 n); mask) { for(int last 0; last n; last) { if(!(mask (1 last))) continue; if(dp[mask][last] INT_MAX) continue; for(int next 0; next n; next) { if(mask (1 next)) continue; int new_mask mask | (1 next); dp[new_mask][next] min(dp[new_mask][next], dp[mask][last] dist[last][next]); } } } return dp[final_state][0]; }5.2 数位DP用于解决与数字各位相关的计数问题如统计区间内满足某种性质的数字个数。5.2.1 不含连续1的数字个数int findIntegers(int num) { string s to_string(num); int n s.size(); vectorvectorint dp(n, vectorint(2, -1)); functionint(int, int, bool) dfs [](int pos, int pre, bool tight) { if(pos n) return 1; if(!tight dp[pos][pre] ! -1) return dp[pos][pre]; int limit tight ? s[pos] - 0 : 1; int res 0; for(int d 0; d limit; d) { if(pre 1 d 1) continue; bool new_tight tight (d limit); res dfs(pos1, d, new_tight); } if(!tight) dp[pos][pre] res; return res; }; return dfs(0, 0, true); }6. 动态规划优化技巧6.1 斜率优化对于形如dp[i] min(dp[j] cost(j,i))的转移方程当cost函数满足某些性质时可以用单调队列优化。6.2 四边形不等式对于区间DP问题当决策点具有单调性时可以优化内层循环。6.3 矩阵快速幂优化当转移方程是线性递推式时可以用矩阵快速幂将时间复杂度从O(n)降到O(logn)。6.3.1 斐波那契数列示例vectorvectorlong long matrixMultiply(vectorvectorlong long a, vectorvectorlong long b) { vectorvectorlong long res(2, vectorlong long(2)); res[0][0] a[0][0]*b[0][0] a[0][1]*b[1][0]; res[0][1] a[0][0]*b[0][1] a[0][1]*b[1][1]; res[1][0] a[1][0]*b[0][0] a[1][1]*b[1][0]; res[1][1] a[1][0]*b[0][1] a[1][1]*b[1][1]; return res; } vectorvectorlong long matrixPower(vectorvectorlong long mat, int n) { vectorvectorlong long res {{1,0},{0,1}}; while(n 0) { if(n % 2 1) { res matrixMultiply(res, mat); } mat matrixMultiply(mat, mat); n / 2; } return res; } int fib(int n) { if(n 0) return 0; vectorvectorlong long mat {{1,1},{1,0}}; auto res matrixPower(mat, n-1); return res[0][0]; }7. 动态规划实战训练建议从简单问题入手理解基本思想大量练习经典DP问题学会将问题转化为DP模型注意边界条件和初始化尝试空间优化参加在线编程比赛实践推荐练习平台洛谷动态规划题单LeetCode动态规划专题Codeforces DP标签题目蓝桥杯历年真题