腾讯云网站建设视频投资5万的小型加工厂

腾讯云网站建设视频,投资5万的小型加工厂,泉州网站制作网页,宣传推广费用预算动态规划#xff08;Dynamic Programming#xff0c;DP#xff09;是算法设计中的核心思想之一#xff0c;核心是将复杂问题分解为重叠的子问题#xff0c;通过存储子问题的解来避免重复计算#xff0c;最终推导出原问题的最优解。以下从核心原理、解题步骤、经典模型到实…动态规划Dynamic ProgrammingDP是算法设计中的核心思想之一核心是将复杂问题分解为重叠的子问题通过存储子问题的解来避免重复计算最终推导出原问题的最优解。以下从核心原理、解题步骤、经典模型到实战案例为你系统拆解动态规划一、动态规划的核心基础1. 核心思想最优子结构原问题的最优解包含其子问题的最优解子问题的解可以组合出原问题的解。重叠子问题求解原问题时会反复遇到相同的子问题若暴力递归会重复计算DP 通过缓存避免。无后效性子问题的解一旦确定不受后续决策影响即当前状态只依赖过去的状态与未来无关。2. 与其他算法的区别算法核心特点适用场景暴力递归直接分解问题无缓存子问题无重叠否则效率极低记忆化搜索递归 缓存自顶向下子问题重叠递归思路清晰动态规划迭代 状态表自底向上子问题重叠需最优解二、动态规划的解题步骤黄金五步1. 定义状态最关键用dp[i]或dp[i][j]表示 “某个子问题的最优解”明确状态的含义例如dp[i]表示前 i 个元素的最大和。状态定义的好坏直接决定 DP 是否能实现需紧扣问题目标。2. 确定状态转移方程描述 “如何从子问题的解推导出原问题的解”即dp[i] f(dp[i-1], dp[i-2], ...)。核心找到当前状态与之前状态的依赖关系。3. 初始化边界条件确定最小子问题的解即 DP 表的初始值例如dp[0] 0、dp[1] nums[0]。边界条件错误会导致整个 DP 表计算错误。4. 确定遍历顺序根据状态转移方程确定计算 DP 表的顺序例如从前到后、从后到前、二维表的行优先 / 列优先。确保计算当前状态时其依赖的子问题已被计算。5. 计算最终结果原问题的解对应 DP 表中的某个位置例如dp[n]或dp[n][m]。三、经典动态规划模型模型 1一维 DP—— 斐波那契数列问题求第 n 个斐波那契数F (0)0, F (1)1, F (n)F (n-1)F (n-2)。步骤拆解状态定义dp[i]表示第 i 个斐波那契数。转移方程dp[i] dp[i-1] dp[i-2]。边界条件dp[0] 0dp[1] 1。遍历顺序从 2 到 n 依次计算。结果dp[n]。int fib(int n) { if (n 1) return n; vectorint dp(n 1); dp[0] 0; dp[1] 1; for (int i 2; i n; i) { dp[i] dp[i-1] dp[i-2]; } return dp[n]; }优化由于只依赖前两个状态可省略 DP 表用变量存储int fib(int n) { if (n 1) return n; int a 0, b 1, c; for (int i 2; i n; i) { c a b; a b; b c; } return b; }模型 2一维 DP—— 最大子数组和LeetCode 53问题给定整数数组 nums找到一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。步骤拆解状态定义dp[i]表示以第 i 个元素结尾的最大子数组和。转移方程dp[i] max(nums[i], dp[i-1] nums[i])要么从当前元素重新开始要么延续前一个子数组。边界条件dp[0] nums[0]。遍历顺序从 1 到 n-1。结果遍历 dp 数组取最大值。int maxSubArray(vectorint nums) { int n nums.size(); vectorint dp(n); dp[0] nums[0]; int result dp[0]; for (int i 1; i n; i) { dp[i] max(nums[i], dp[i-1] nums[i]); result max(result, dp[i]); } return result; }优化省略 DP 表用变量存储当前状态int maxSubArray(vectorint nums) { int cur_sum nums[0], max_sum nums[0]; for (int i 1; i nums.size(); i) { cur_sum max(nums[i], cur_sum nums[i]); max_sum max(max_sum, cur_sum); } return max_sum; }模型 3二维 DP—— 不同路径LeetCode 62问题一个机器人从 m×n 网格的左上角出发每次只能向下或向右移动到达右下角共有多少条不同路径步骤拆解状态定义dp[i][j]表示从 (0,0) 到 (i,j) 的路径数。转移方程dp[i][j] dp[i-1][j] dp[i][j-1]只能从上方或左方到达。边界条件第一行dp[0][j] 1只能从左方来。第一列dp[i][0] 1只能从上方来。遍历顺序行优先遍历从上到下从左到右。结果dp[m-1][n-1]。int uniquePaths(int m, int n) { vectorvectorint dp(m, vectorint(n, 1)); // 初始化边界为1 for (int i 1; i m; i) { for (int j 1; j n; j) { dp[i][j] dp[i-1][j] dp[i][j-1]; } } return dp[m-1][n-1]; }优化用一维数组压缩空间只保留上一行的状态int uniquePaths(int m, int n) { vectorint dp(n, 1); for (int i 1; i m; i) { for (int j 1; j n; j) { dp[j] dp[j-1]; // 等价于 dp[i][j] dp[i-1][j] dp[i][j-1] } } return dp[n-1]; }模型 4二维 DP——0-1 背包问题问题有 n 件物品每件物品的重量为 w [i]价值为 v [i]背包容量为 C求能装入背包的最大价值每件物品只能选一次。步骤拆解状态定义dp[i][j]表示前 i 件物品背包容量为 j 时的最大价值。转移方程不选第 i 件物品dp[i][j] dp[i-1][j]。选第 i 件物品需 j ≥ w [i]dp[i][j] dp[i-1][j - w[i]] v[i]。最终dp[i][j] max(不选, 选)。边界条件dp[0][j] 0无物品时价值为 0。dp[i][0] 0容量为 0 时价值为 0。遍历顺序物品从 1 到 n容量从 1 到 C。结果dp[n][C]。int knapsack(vectorint w, vectorint v, int C) { int n w.size(); vectorvectorint dp(n1, vectorint(C1, 0)); for (int i 1; i n; i) { for (int j 1; j C; j) { if (j w[i-1]) { // 容量不足无法选第i件注意w[i-1]是第i件物品的重量 dp[i][j] dp[i-1][j]; } else { dp[i][j] max(dp[i-1][j], dp[i-1][j - w[i-1]] v[i-1]); } } } return dp[n][C]; }优化一维数组压缩容量需从后往前遍历避免覆盖未计算的状态int knapsack(vectorint w, vectorint v, int C) { int n w.size(); vectorint dp(C1, 0); for (int i 0; i n; i) { // 遍历物品 for (int j C; j w[i]; --j) { // 从后往前遍历容量 dp[j] max(dp[j], dp[j - w[i]] v[i]); } } return dp[C]; }四、动态规划的常见优化技巧空间压缩一维 DP→变量如斐波那契。二维 DP→一维 DP如背包、不同路径。仅保留必要的状态丢弃无关的历史数据。状态合并合并重复的状态定义减少 DP 表维度例如将两个相关状态合并为一个。单调队列优化适用于状态转移涉及区间最值的问题如滑动窗口最大值、多重背包。滚动数组对于只依赖前 k 层的二维 DP用 k1 个数组循环使用如三维 DP 压缩为二维。五、动态规划的学习建议从基础模型入手先掌握斐波那契、最大子数组和、背包、路径问题等经典模型理解状态定义和转移的逻辑。多做分类练习按 “一维 DP→二维 DP→区间 DP→树形 DP→状态压缩 DP” 的顺序进阶。手动推导 DP 表对每个问题先手动计算小案例的 DP 表如 n3、m2再写代码。对比暴力与 DP理解 DP 如何通过缓存解决重叠子问题避免重复计算。总结状态转移规律例如 “以 i 结尾”“前 i 个元素”“到达 (i,j)” 等常见状态定义方式。提炼与总结动态规划的核心是状态定义 状态转移状态定义是 “灵魂”转移方程是 “核心”。解题关键将问题转化为 “子问题的最优解组合”用 DP 表存储子问题解避免重复计算。优化核心减少 DP 表的维度空间或减少状态转移的计算量时间。