算法动态规划概述动态规划Dynamic Programming, DP是一种解决多阶段决策最优化问题的算法思想。其产生的直接背景是传统递归分治在处理重叠子问题时存在大量重复计算如斐波那契数列复杂度 O(2ⁿ)。DP 通过保存已解决子问题的结果避免重复计算将指数级复杂度降为多项式级如 O(n²)。动态规划 暴力递归 备忘录记忆化 表格化顺序计算 状态压缩其中•动态决策过程是多阶段的当前决策会影响未来状态。•规划在给定约束下寻找最优方案。场景使用 DP 必须同时满足以下两个条件条件定义最优子结构原问题的最优解包含子问题的最优解重叠子问题不同阶段会反复使用相同的子问题解若不满足最优子结构如有环图最长路径DP 无效若不满足重叠子问题如快速排序DP 无性能收益。特点•空间换时间额外存储子问题解避免重复计算子问题减少时间复杂度。•保证全局最优只要问题满足最优子结构DP保证找到全局最优解。•可压缩性DP 表通常可降维滚动数组适合嵌入式内存受限环境。核心DP 的核心由四个要素组成1.状态用变量如dp[i]或dp[i][j]描述子问题。状态空间大小直接决定内存需求。2.状态转移方程描述当前状态与之前状态的关系如dp[i] f(dp[i-1], ...)。3.边界条件最小子问题的解作为递推的起始值。4.计算顺序确保计算当前状态时其依赖的状态已经完成。注意这里类似嵌入式中的状态机机制。分析按以下四步完成 DP 问题的分析1.定义状态明确dp[i]或dp[i][j]的含义尽量精简状态维度。2.推导转移方程分析当前状态与前面状态的关系写出数学表达式。3.确定边界找到递推起点如dp[0]、dp[n-1][j]等。4.确定计算顺序根据依赖关系决定从小到大、从大到小、从上到下等顺序。示例爬楼梯有n级台阶每次可以跨 1 级或 2 级。问爬到第n级总共有多少种不同的方法。分析• 状态dp[i]表示爬到第i级台阶的方法总数。i从 0 到 n。• 转移要到达第i级要么从第i-1级跨 1 级上来要么从第i-2级跨 2 级上来。dp[i] dp[i-1] dp[i-2]i ≥ 3)• 边界dp[0] 1站在地面1 种方法即不动dp[1] 1只能跨 1 级dp[2] 2可以跨 2 次每次跨 1 级或者跨 1 次跨 2 级• 顺序从第 1 级台阶向上迭代。代码/* * * 爬楼梯问题有 n 级台阶 * 每次可以跨 1 级或 2 级。问爬到第 n 级总共有多少种不同的方法 * n - 需要求解的最终台阶位置 * 返回爬到 n 级台阶的方法总和 * */ int climb_stairs(int n) { /* 状态定义dp[i] 表示爬到第 i 级台阶的方法总和 */ int i, dp[MAX_STAIR1] { 0 }; if (n MAX_STAIR - 1) return -1; /* 边界条件 */ dp[0] 1; /* 原地不动值并无什么实际意义 */ dp[1] 1; /* 上第一级台阶只有一种方法 */ dp[2] 2; /* 上第二级台阶可以分两次每次上一级也可一次上2级台阶*/ /* 状态转移方程dp[i] dp[i-1] dp[i-2] 到达i级台阶的方法从i-1级台阶跨1步或者从i-2级台阶跨2步 */ for (i3; in; i) { dp[i] dp[i-2] dp[i-1]; } return (dp[n]); }优化分析当前台阶只与前两级台阶的值有关从节省内存角度出发不考虑记录所有台阶的值只保存最新 2 级台阶的值即可。/* * * 爬楼梯问题优化当前台阶只与前两级台阶的值有关 * 从节省内存角度出发不考虑记录所有台阶的值只保存最新2级台阶的值即可 * n - 需要求解的最终台阶位置 * 返回爬到 n 级台阶的方法总和 * */ int climb_stairs_optimize(int n) { /* pre_2、pre_1 分别记录爬到当前台阶的前两级、前一级方法总和值 */ int i, pre_2, pre_1, curr; /* 边界条件 */ pre_2 1; /* 上第一级台阶只有一种方法 */ pre_1 2; /* 上第二级台阶可以分两次每次上一级也可一次上2级台阶*/ /* 状态转移方程curr pre_2 pre_1 */ for (i3; in; i) { curr pre_2 pre_1; /* 更新前两级台阶方法值为下一次计算做准备 */ pre_2 pre_1; pre_1 curr; } return (curr); }最大子数组和给定一个整数数组nums找出一个连续子数组至少包含一个元素使该子数组的和最大返回这个最大和。分析• 状态dp[i]表示以第i个元素结尾的连续子数组的最大和。• 转移对于nums[i]要么把它接到前面的子数组后面dp[i-1] nums[i]要么自己单独成为一个新子数组nums[i]。取较大者。dp[i] max(dp[i-1] nums[i], nums[i])• 边界dp[0] nums[0]以第一个元素结尾的子数组只能是它自己• 顺序从第 1 个元素向后迭代。代码/* * * 最大子数组和问题给定一个整数数组nums * 找出一个连续子数组至少包含一个元素使该子数组的和最大返回这个最大和。 * nums - 数据 n - 元素个数 * 返回最大连续子数组和 * */ int max_sub_array_sum(int *nums, int n) { /* 状态定义dp[i] 表示以第 i 个元素结尾的连续子数组的最大和 */ int i, max, dp[MAX_ARR_NUM1] { 0 }; if (n MAX_ARR_NUM - 1) return -1; /* 边界条件 */ dp[0] nums[0]; /* 第一个元素结尾的子链就是它自己 */ max dp[0]; /* 记录最大连续子数组和 */ /* 状态转移方程dp[i] MAX(dp[i-1]nums[i], nums[i]) 当前最大值取接上一个子数组或者单独成新子数组的最大值 */ for (i1; in; i) { dp[i] MAX(dp[i-1]nums[i], nums[i]); max MAX(dp[i], max); } return (max); }优化当前元素下的数组最大值只与上一个元素结尾子数组的最大值有关从节省内存角度出发不考虑记录所有元素结尾子数组的值只保存上一个元素结尾子数组最大值即可。/* * * 最大子数组和问题优化当前元素下的数组最大值只与上一个元素结尾子数组的最大值有关 * 从节省内存角度出发不考虑记录所有元素结尾子数组的值只保存上一个元素结尾子数组最大值即可 * nums - 数据 n - 元素个数 * 返回最大连续子数组和 * */ int max_sub_array_sum_optimize(int *nums, int n) { /* pre表示上一个元素最大值 */ int i, pre, max; /* 边界条件 */ pre nums[0]; /* 第一个元素就是当前最大值 */ max nums[0]; /* 记录最大子数组和的值 */ /* 状态转移方程curr pre_2 pre_1 */ for (i1; in; i) { pre MAX(prenums[i], nums[i]); max MAX(pre, max); } return (max); }不同路径一个机器人位于m x n网格的左上角起点(0,0)它每次只能向右或向下移动一步要到达右下角(m-1, n-1)。问总共有多少条不同的路径分析• 状态dp[i][j]表示从起点(0,0)走到格子(i,j)的不同路径数。• 转移要到达(i,j)只能从它的上方(i-1,j)向下走一步或者从左方(i,j-1)向右走一步。因此dp[i][j] dp[i-1][j] dp[i][j-1]当i0且j0• 边界第一行(0,j)只能一直向右所以dp[0][j] 1第一列(i,0)只能一直向下所以dp[i][0] 1dp[0][0] 1• 顺序从第 00出发迭代。代码/* * * 不同路径问题一个机器人位于m x n网格的左上角起点 (0,0) * 它每次只能向右或向下移动一步要到达右下角 (m-1, n-1)。问总共有多少条不同的路径 * m - 网格行数 n - 网格列数 * 返回不同路径数量总和 * */ int unique_paths(int m, int n) { /* 状态定义dp[i][j] 表示到达格子(i,j)有多少条路径 */ int i, j, dp[MAX_ARR_NUM1][MAX_ARR_NUM1] { {0} }; if ((n MAX_ARR_NUM - 1) || (m MAX_ARR_NUM - 1)) return -1; /* 边界条件,第 1 行和第 1 列都只有一种路径 */ for (i0; im; i) dp[i][0] 1; for (i0; in; i) dp[0][i] 1; /* 状态转移方程dp[i][j] dp[i-1][j] dp[i][j-1]; 要到达当前格子的方法到达上边格子的方法到达右边格子的方法 */ for (i1; im; i) { for (j1; jn; j) { dp[i][j] dp[i-1][j] dp[i][j-1]; } } return (dp[m-1][n-1]); }优化将二维数组压缩成一维逐行计算各个格子不同路径总数此时计算(i, j)格子时(i, j-1)的格子左边已更新未更新的(i, j)实际存储为上面的格子的路径数。/* * * 不同路径问题优化将二维数组压缩成一维逐行计算各个格子不同路径总数 * 此时计算(i,j)格子时(i,j-1)的格子左边已更新未更新的(i,j)实际存储为上面的格子的路径数 * m - 网格行数 n - 网格列数 * 返回不同路径数量总和 * */ int unique_paths_optimize(int m, int n) { /* 状态定义dp[i] 表示到达指定格子有多少条路径每次存储一行的数据 */ int i, j, dp[MAX_ARR_NUM1] {0}; if (n MAX_ARR_NUM - 1) return -1; /* 边界条件,第 1 行只有一种路径 */ for (j0; jn; j) dp[j] 1; /* 状态转移方程dp[j] dp[j-1](右边) dp[j]上边; 要到达当前格子的方法到达上边格子的方法到达右边格子的方法 */ for (i1; im; i) { for (j1; jn; j) { dp[j] dp[j-1] dp[j]; } } return (dp[n-1]); }0-1 背包问题有N件物品和一个容量为W的背包。第i件物品的重量是wt[i]价值是val[i]。每件物品只能选一次0-1 背包。求在不超过背包容量的前提下能装入的最大总价值。分析• 状态dp[i][j]表示考虑前i件物品索引 1~i背包容量为j时能获得的最大价值。• 转移对于第i件物品重量wt[i-1]价值val[i-1]有两种选择取两者最大值dp[i][j] max(dp[i-1][j], dp[i-1][j - wt[i-1]] val[i-1])当j ≥ wt[i-1]不装dp[i][j] dp[i-1][j]装前提j ≥ wt[i-1]dp[i][j] dp[i-1][j - wt[i-1]] val[i-1]• 边界第一行没有物品可选价值为0。所以dp[0][j] 0第一列容量为0价值为0。所以dp[i][0] 0• 顺序从dp[1][1]开始顺序迭代。代码/* * * 0-1背包问题有N件物品和一个容量为W的背包。第i件物品的重量是wt[i]价值是val[i]。 * 每件物品只能选一次0-1 背包。求在不超过背包容量的前提下能装入的最大总价值。 * W - 容量上限 wt - 物品重量 N - 物品数 val - 物品价值 * 返回最大总价值 * */ int knapsack(int W, int wt[], int N, int val[]) { /* 状态定义dp[i][j] 表示考虑前 i 件物品重量不超过 j 的最大价值 */ int i, j, dp[MAX_N1][MAX_C1] { {0} }; if ((N MAX_N - 1) || (W MAX_C - 1)) return -1; /* 边界条件,背包重量限制为0时或者背包没有物品时价值均为0 */ for (i0; iN; i) dp[i][0] 0; for (j0; jW; j) dp[0][j] 0; /* 状态转移方程dp[i][j] MAX(dp[i-1][j], dp[i-1][j-wt[i-1]] val[i-1]) 面对第 i 件物品(wt[i-1], val[i-1])取不装dp[i-1][j]或者装dp[i-1][j-wt[i-1]]val[i-1]的最大值 */ for (i1; iN; i) { for (jW; jwt[i-1]; j--) dp[i][j] MAX(dp[i-1][j], dp[i-1][j-wt[i-1]] val[i-1]); } return (dp[N][W]); }优化观察计算dp[i][j]时只用到了第 i-1 行的dp[i-1][j]和dp[i-1][j - wt[i-1]]。也就是只依赖上一行的数据不会用到更早的行。所以我们只需要保留一行当前正在计算的行就够了。注意当你计算dp[j]时右边的dp[j - wt[i]]可能是已经更新过的因为容量小先算。如果dp[j - wt[i]]已经包含了当前物品i那么dp[j]就会再次尝试加入物品i相当于同一物品可以用多次这就变成了完全背包而不是 0-1 背包每个物品只能用一次。所以我们只能倒叙遍历保证j - wt[i-1]更新在j更新之后。/* * * 0-1背包问题优化观察上述状态转移方程dp[i][j] MAX(dp[i-1][j], dp[i-1][j-wt[i-1]] val[i-1]) * 计算dp[i][j]时只用到了第i-1行的dp[i-1][j]和dp[i-1][j - wt[i-1]]。 * 即只依赖上一行的数据不会用到更早的行。所以我们只需要保留一行当前正在计算的行就够了。 * 注意j-wt[i-1] j,如果顺序遍历计算j重量的时候j - wt[i-1]必然已经更新过此时会变成完全背包。 * 所以我们只能倒叙遍历保证j - wt[i-1]更新在j更新之后。 * W - 容量上限 wt - 物品重量 N - 物品数 val - 物品价值 * 返回最大总价值 * */ int knapsack_optimize(int W, int wt[], int N, int val[]) { /* 状态定义dp[i] 表示考虑单个物品不同重量下的最大价值 */ int i, j, dp[MAX_C1] {0}; if (W MAX_C - 1) return -1; /* 边界条件,背包没有物品时价值为0 */ for (i0; iW; i) dp[i] 0; /* 状态转移方程dp[j] MAX(dp[j], dp[j-wt[i-1]] val[i-1]); 商品最大价值 取装与不装分别获取的价值的最大值 */ for (i1; iN; i) { for (jW; jwt[i-1]; j--) dp[j] MAX(dp[j], dp[j-wt[i-1]] val[i-1]); } return (dp[W]); }总结动态规划是一种“填表”算法它把大问题拆成一系列相互依赖的子问题自底向上或自顶向下带备忘录依次计算出每个子问题的答案最终组合出原问题的解。它的时间复杂度通常与状态数量呈多项式关系远优于指数级的暴力递归。DP 是解决重叠子问题最优化问题的标准方法核心四要素状态、转移方程、边界、顺序。步骤要回答的问题1. 状态用几个变量维度能描述子问题如dp[i]或dp[i][j]2. 转移当前状态 前面某些状态的某种组合、max、min等3. 边界边界i0、j0、容量0 时的值是什么4. 顺序最终确定递推方向从下往上从每行左到右?注意计算顺序不唯一。你也可以从上往下但状态定义和转移方程会变比如定义为从顶部走到(i,j)的最大和。两种顺序都可以但边界不同。完整代码/** * Filename : study_dp.c * Revision : $Revision: 1.00 $ * Author : Feng(更多编程相关的知识和源码见微信公众号不只会拍照的程序猿欢迎订阅) * Description : 动态规划学习 **/ #include stdio.h #include string.h #define MAX_STAIR 30 /* 台阶最大值 */ #define MAX_ARR_NUM 30 /* 数组最大值 */ #define MAX_N 10 /* 最大物品数量 */ #define MAX_C 30 /* 最大背包重量 */ #define MAX(x, y) (x) (y) ? (x) : (y) #define MIN(x, y) (x) (y) ? (x) : (y) #define ARR_SIZE(x) sizeof(x)/sizeof(x[0]) /* * * 爬楼梯问题有 n 级台阶 * 每次可以跨 1 级或 2 级。问爬到第 n 级总共有多少种不同的方法 * n - 需要求解的最终台阶位置 * 返回爬到 n 级台阶的方法总和 * */ int climb_stairs(int n) { /* 状态定义dp[i] 表示爬到第 i 级台阶的方法总和 */ int i, dp[MAX_STAIR1] { 0 }; if (n MAX_STAIR - 1) return -1; /* 边界条件 */ dp[0] 1; /* 原地不动值并无什么实际意义 */ dp[1] 1; /* 上第一级台阶只有一种方法 */ dp[2] 2; /* 上第二级台阶可以分两次每次上一级也可一次上2级台阶*/ /* 状态转移方程dp[i] dp[i-1] dp[i-2] 到达i级台阶的方法从i-1级台阶跨1步或者从i-2级台阶跨2步 */ for (i3; in; i) { dp[i] dp[i-2] dp[i-1]; } return (dp[n]); } /* * * 爬楼梯问题优化当前台阶只与前两级台阶的值有关 * 从节省内存角度出发不考虑记录所有台阶的值只保存最新2级台阶的值即可 * n - 需要求解的最终台阶位置 * 返回爬到 n 级台阶的方法总和 * */ int climb_stairs_optimize(int n) { /* pre_2、pre_1 分别记录爬到当前台阶的前两级、前一级方法总和值 */ int i, pre_2, pre_1, curr; /* 边界条件 */ pre_2 1; /* 上第一级台阶只有一种方法 */ pre_1 2; /* 上第二级台阶可以分两次每次上一级也可一次上2级台阶*/ /* 状态转移方程curr pre_2 pre_1 */ for (i3; in; i) { curr pre_2 pre_1; /* 更新前两级台阶方法值为下一次计算做准备 */ pre_2 pre_1; pre_1 curr; } return (curr); } /* * * 最大子数组和问题给定一个整数数组nums * 找出一个连续子数组至少包含一个元素使该子数组的和最大返回这个最大和。 * nums - 数据 n - 元素个数 * 返回最大连续子数组和 * */ int max_sub_array_sum(int *nums, int n) { /* 状态定义dp[i] 表示以第 i 个元素结尾的连续子数组的最大和 */ int i, max, dp[MAX_ARR_NUM1] { 0 }; if (n MAX_ARR_NUM - 1) return -1; /* 边界条件 */ dp[0] nums[0]; /* 第一个元素结尾的子链就是它自己 */ max dp[0]; /* 记录最大连续子数组和 */ /* 状态转移方程dp[i] MAX(dp[i-1]nums[i], nums[i]) 当前最大值取接上一个子数组或者单独成新子数组的最大值 */ for (i1; in; i) { dp[i] MAX(dp[i-1]nums[i], nums[i]); max MAX(dp[i], max); } return (max); } /* * * 最大子数组和问题优化当前元素下的数组最大值只与上一个元素结尾子数组的最大值有关 * 从节省内存角度出发不考虑记录所有元素结尾子数组的值只保存上一个元素结尾子数组最大值即可 * nums - 数据 n - 元素个数 * 返回最大连续子数组和 * */ int max_sub_array_sum_optimize(int *nums, int n) { /* pre表示上一个元素最大值 */ int i, pre, max; /* 边界条件 */ pre nums[0]; /* 第一个元素就是当前最大值 */ max nums[0]; /* 记录最大子数组和的值 */ /* 状态转移方程curr pre_2 pre_1 */ for (i1; in; i) { pre MAX(prenums[i], nums[i]); max MAX(pre, max); } return (max); } /* * * 不同路径问题一个机器人位于m x n网格的左上角起点 (0,0) * 它每次只能向右或向下移动一步要到达右下角 (m-1, n-1)。问总共有多少条不同的路径 * m - 网格行数 n - 网格列数 * 返回不同路径数量总和 * */ int unique_paths(int m, int n) { /* 状态定义dp[i][j] 表示到达格子(i,j)有多少条路径 */ int i, j, dp[MAX_ARR_NUM1][MAX_ARR_NUM1] { {0} }; if ((n MAX_ARR_NUM - 1) || (m MAX_ARR_NUM - 1)) return -1; /* 边界条件,第 1 行和第 1 列都只有一种路径 */ for (i0; im; i) dp[i][0] 1; for (i0; in; i) dp[0][i] 1; /* 状态转移方程dp[i][j] dp[i-1][j] dp[i][j-1]; 要到达当前格子的方法到达上边格子的方法到达右边格子的方法 */ for (i1; im; i) { for (j1; jn; j) { dp[i][j] dp[i-1][j] dp[i][j-1]; } } return (dp[m-1][n-1]); } /* * * 不同路径问题优化将二维数组压缩成一维逐行计算各个格子不同路径总数 * 此时计算(i,j)格子时(i,j-1)的格子左边已更新未更新的(i,j)实际存储为上面的格子的路径数 * m - 网格行数 n - 网格列数 * 返回不同路径数量总和 * */ int unique_paths_optimize(int m, int n) { /* 状态定义dp[i] 表示到达指定格子有多少条路径每次存储一行的数据 */ int i, j, dp[MAX_ARR_NUM1] {0}; if (n MAX_ARR_NUM - 1) return -1; /* 边界条件,第 1 行只有一种路径 */ for (j0; jn; j) dp[j] 1; /* 状态转移方程dp[j] dp[j-1](右边) dp[j]上边; 要到达当前格子的方法到达上边格子的方法到达右边格子的方法 */ for (i1; im; i) { for (j1; jn; j) { dp[j] dp[j-1] dp[j]; } } return (dp[n-1]); } /* * * 0-1背包问题有N件物品和一个容量为W的背包。第i件物品的重量是wt[i]价值是val[i]。 * 每件物品只能选一次0-1 背包。求在不超过背包容量的前提下能装入的最大总价值。 * W - 容量上限 wt - 物品重量 N - 物品数 val - 物品价值 * 返回最大总价值 * */ int knapsack(int W, int wt[], int N, int val[]) { /* 状态定义dp[i][j] 表示考虑前 i 件物品重量不超过 j 的最大价值 */ int i, j, dp[MAX_N1][MAX_C1] { {0} }; if ((N MAX_N - 1) || (W MAX_C - 1)) return -1; /* 边界条件,背包重量限制为0时或者背包没有物品时价值均为0 */ for (i0; iN; i) dp[i][0] 0; for (j0; jW; j) dp[0][j] 0; /* 状态转移方程dp[i][j] MAX(dp[i-1][j], dp[i-1][j-wt[i-1]] val[i-1]) 面对第 i 件物品(wt[i-1], val[i-1])取不装dp[i-1][j]或者装dp[i-1][j-wt[i-1]]val[i-1]的最大值 */ for (i1; iN; i) { for (jW; jwt[i-1]; j--) dp[i][j] MAX(dp[i-1][j], dp[i-1][j-wt[i-1]] val[i-1]); } return (dp[N][W]); } /* * * 0-1背包问题优化观察上述状态转移方程dp[i][j] MAX(dp[i-1][j], dp[i-1][j-wt[i-1]] val[i-1]) * 计算dp[i][j]时只用到了第i-1行的dp[i-1][j]和dp[i-1][j - wt[i-1]]。 * 即只依赖上一行的数据不会用到更早的行。所以我们只需要保留一行当前正在计算的行就够了。 * 注意j-wt[i-1] j,如果顺序遍历计算j重量的时候j - wt[i-1]必然已经更新过此时会变成完全背包。 * 所以我们只能倒叙遍历保证j - wt[i-1]更新在j更新之后。 * W - 容量上限 wt - 物品重量 N - 物品数 val - 物品价值 * 返回最大总价值 * */ int knapsack_optimize(int W, int wt[], int N, int val[]) { /* 状态定义dp[i] 表示考虑单个物品不同重量下的最大价值 */ int i, j, dp[MAX_C1] {0}; if (W MAX_C - 1) return -1; /* 边界条件,背包没有物品时价值为0 */ for (i0; iW; i) dp[i] 0; /* 状态转移方程dp[j] MAX(dp[j], dp[j-wt[i-1]] val[i-1]); 商品最大价值 取装与不装分别获取的价值的最大值 */ for (i1; iN; i) { for (jW; jwt[i-1]; j--) dp[j] MAX(dp[j], dp[j-wt[i-1]] val[i-1]); } return (dp[W]); } int main(void) { int n 11; int r 3, c 7; int nums[] {-2, 1, -3, 4, -1, 2, 1, -5, 4}; int W 10; // 背包容量 int wt[] {2, 3, 4, 5}; // 物品重量 int val[] {3, 4, 5, 6}; // 物品价值 int N ARR_SIZE(wt); int size ARR_SIZE(nums); printf(爬 %d 级台阶的方法数: %d\n, n, climb_stairs(n)); printf(爬 %d 级台阶的方法数优化版本: %d\n, n, climb_stairs_optimize(n)); printf(最大子数组和: %d\n, max_sub_array_sum(nums, size)); printf(最大子数组和优化版本: %d\n, max_sub_array_sum_optimize(nums, size)); printf(%dx%d 网格的不同路径数: %d\n, r, c, unique_paths(r, c)); printf(%dx%d 网格的不同路径数优化版本: %d\n, r, c, unique_paths_optimize(r, c)); printf(最大背包价值: %d\n, knapsack(W, wt, N, val)); printf(最大背包价值优化版本: %d\n, knapsack_optimize(W, wt, N, val)); return 0; }运行结果
