跳到主要内容 动态规划算法详解：从基础概念到经典例题 | 极客日志
C++ 算法
动态规划算法详解：从基础概念到经典例题 介绍动态规划（DP）算法，通过六个经典例题讲解其核心思想。涵盖状态表示、状态转移方程、初始化及填表顺序。例题包括第 N 个泰波那契数、三步问题、最小花费爬楼梯、解码方法以及不同路径系列。提供 C++ 代码实现，重点解决溢出处理与边界条件，帮助读者掌握线性 DP 与二维 DP 的解题套路。
NodeJser 发布于 2026/3/27 更新于 2026/4/16 在计算机科学中，动态规划（Dynamic Programming，简称 DP）是解决最优化问题的一种重要方法。通过将大问题拆解为小问题，动态规划不仅能够显著降低计算复杂度，还能提高效率。无论是经典的背包问题，还是更加复杂的路径最短问题，动态规划都能提供优雅且高效的解法。
本文将带领你走进动态规划的世界，从基础概念到实际应用，逐步揭开这一算法的神秘面纱。无论你是算法新手，还是希望深入理解动态规划背后原理的开发者，本文都将为你提供清晰的思路和具体的示例。
1. 第 N 个泰波那契数
题目链接
1137. 第 N 个泰波那契数 - 力扣（LeetCode）
解法（动态规划）
算法流程
状态表示：
这道题可以根据题目的要求直接定义出状态表示：
dp[i] 表示：第 i 个泰波那契数的值。
状态转移方程：
题目已经非常贴心地告诉我们了：
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
初始化：
从我们的递推公式可以看出，dp[i] 在 i = 0 以及 i = 1 的时候没有办法进行推导的，因为 dp[-2] 或 dp[-1] 不是一个有效的数据。
因此我们需要在填表之前，将 0, 1, 2 位置的值初始化。题目中已经告诉我们 dp[0] = 0, dp[1] = dp[2] = 1。
填表顺序：
毫无疑问是「从左往右」。
返回值：
应该返回 dp[n] 的值。
C++ 算法代码
使用一维数组：
class Solution {
public :
int tribonacci (int n) vector<int > v (n + 1 ) ;
if (n >= 0 ) v[0 ] = 0 ;
if (n >= 1 ) v[1 ] = 1 ;
if (n >= 2 ) v[2 ] = 1 ;
for (int i = 微信扫一扫，关注极客日志 微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具 加密/解密文本 使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码 将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器 将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
Markdown转HTML 将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
HTML转Markdown 将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
JSON 压缩 通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
3
1
2
3
return
2. 三步问题
题目链接
解法（动态规划）
状态表示
这道题可以根据「经验 + 题目要求」直接定义出状态表示：dp[i] 表示：到达 i 位置时，一共有多少种方法。
状态转移方程
以 i 位置状态的最近的一步，来分情况讨论：
如果 dp[i] 表示小孩上第 i 阶楼梯的所有方式，那么它应该等于所有上一步的方式之和：
i. 上一步上一级台阶，dp[i] += dp[i - 1]；
ii. 上一步上两级台阶，dp[i] += dp[i - 2]；
iii. 上一步上三级台阶，dp[i] += dp[i - 3]；
综上所述，dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]。
需要注意的是，这道题目说，由于结果可能很大，需要对结果取模。在计算的时候，三个值全部加起来再取模，即 (dp[i - 1] + dp[i - 2] + dp[i - 3]) % MOD 是不可取的，同学们可以试验一下，n 取题目范围内最大值时，网站会报错 signed integer overflow。
对于这类需要取模的问题，我们每计算一次（两个数相加/乘等），都需要取一次模。否则，万一发生了溢出，我们的答案就错了。
初始化
从我们的递推公式可以看出，dp[i] 在 i = 0, i = 1 以及 i = 2 的时候没有办法进行推导的，因为 dp[-3] dp[-2] 或 dp[-1] 不是一个有效的数据。 因此我们需要在填表之前，将 1, 2, 3 位置的值初始化。根据题意，dp[1] = 1, dp[2] = 2, dp[3] = 4。
填表顺序
毫无疑问是「从左往右」。
返回值
应该返回 dp[n] 的值。
代码实现 class Solution {
public :
const int MOD = 1e9 + 7 ;
int waysToStep (int n) if (n == 1 || n == 2 ) return n;
if (n == 3 ) return 4 ;
vector<int > dp (n + 1 ) ;
dp[1 ] = 1 , dp[2 ] = 2 , dp[3 ] = 4 ;
for (int i = 4 ; i <= n; i++)
dp[i] = ((dp[i - 1 ] + dp[i - 2 ]) % MOD + dp[i - 3 ]) % MOD;
return dp[n];
}
};
3. 使用最小花费爬楼梯
题目链接
解法（动态规划）
状态表示：
这道题可以根据「经验 + 题目要求」直接定义出状态表示：第一种：以 i 位置为结尾， dp[i] 表示：到达 i 位置时的最小花费。（注意：到达 i 位置的时候，i 位置的钱不需要算上）
▪ 先到达 i - 1 的位置，然后支付 cost[i - 1]，接下来走一步走到 i 位置：
▪ 先到达 i - 2 的位置，然后支付 cost[i - 2]，接下来走一步走到 i 位置：
初始化：
从我们的递推公式可以看出，我们需要先初始化 i = 0，以及 i = 1 位置的值。容易得到 dp[0] = dp[1] = 0，因为不需要任何花费，就可以直接站在第 0 层和第 1 层上。
填表顺序：
根据「状态转移方程」可得，遍历的顺序是「从左往右」。
返回值：
根据「状态表示以及题目要求」，需要返回 dp[n] 位置的值。
C++ 算法代码： class Solution {
public :
int minCostClimbingStairs (vector<int >& cost) int n = cost.size ();
vector<int > dp (n + 1 , 0 ) ;
for (int i = 2 ; i < n + 1 ; i++)
dp[i] = min (cost[i - 1 ] + dp[i - 1 ], cost[i - 2 ] + dp[i - 2 ]);
return dp[n];
}
};
状态表示：
这道题可以根据「经验 + 题目要求」直接定义出状态表示：第二种：以 i 位置为起点， dp[i] 表示：从 i 位置出发，到达楼顶，此时的最小花费 。
▪ 支付 cost[i]，往后走一步，接下来从 i + 1 的位置出发到终点：dp[i + 1] + cost[i]；
▪ 支付 cost[i]，往后走两步，接下来从 i + 2 的位置出发到终点：dp[i + 2] + cost[i]；
我们要的是最小花费，因此 dp[i] = min(dp[i + 1], dp[i + 2]) + cost[i]。
初始化：
为了保证填表的时候不越界，我们需要初始化最后两个位置的值，结合状态表示易得：dp[n - 1] = cost[n - 1], dp[n - 2] = cost[n - 2]
填表顺序：
根据「状态转移方程」可得，遍历的顺序是「从右往左」。
返回值：
根据「状态表示以及题目要求」，需要返回 dp[n] 位置的值。
class Solution {
public :
int minCostClimbingStairs (vector<int >& cost) int n = cost.size ();
vector<int > dp (n) ;
dp[n - 1 ] = cost[n - 1 ], dp[n - 2 ] = cost[n - 2 ];
for (int i = n - 3 ; i >= 0 ; i--)
dp[i] = min (dp[i + 1 ], dp[i + 2 ]) + cost[i];
return min (dp[0 ], dp[1 ]);
}
};
4. 解码方法
题目链接
解法（动态规划）：
状态表示：
类似于斐波那契数列~ 1. 状态表示： 根据以往的经验，对于大多数线性 dp，我们经验上都是「以某个位置结束或者开始」做文章，这里我们继续尝试「用 i 位置为结尾」结合「题目要求」来定义状态表示。
dp[i] 表示：字符串中 [0，i] 区间上，一共有多少种编码方法。
状态转移方程：
定义好状态表示，我们就可以分析 i 位置的 dp 值，如何由「前面」或者「后面」的信息推导来。关于 i 位置的编码状况，我们可以分为下面两种情况： i. 让 i 位置上的数单独解码成一个字母；
ii. 让 i 位置上的数与 i - 1 位置上的数结合，解码成一个字母。
让 i 位置上的数单独解码成一个字母，就存在「解码成功」和「解码失败」两种情况：
i. 解码成功：当 i 位置上的数在 [1, 9] 之间的时候，说明 i 位置上的数是可以单独解码的，那么此时 [0, i] 区间上的解码方法应该等于 [0, i - 1] 区间上的解码方法。因为 [0, i - 1] 区间上的所有解码结果，后面填上一个 i 位置解码后的字母就可以了。此时 dp[i] = dp[i - 1] ；
ii. 解码失败：当 i 位置上的数是 0 的时候，说明 i 位置上的数是不能单独解码的，那么此时 [0, i] 区间上不存在解码方法。因为 i 位置如果单独参与解码，但是解码失败了，那么前面做的努力就全部白费了。此时 dp[i] = 0。
让 i 位置上的数与 i - 1 位置上的数结合在一起，解码成一个字母，也存在「解码成功」和「解码失败」两种情况：
i. 解码成功：当结合的数在 [10, 26] 之间的时候，说明 [i - 1, i] 两个位置是可以解码成功的，那么此时 [0, i] 区间上的解码方法应该等于 [0, i - 2] 区间上的解码方法，原因同上。此时 dp[i] = dp[i - 2]；
ii. 解码失败：当结合的数在 [0, 9] 和 [27 , 99] 之间的时候，说明两个位置结合后解码失败（这里一定要注意 00 01 02 03 04 ...... 这几种情况），那么此时 [0, i] 区间上的解码方法就不存在了，原因依旧同上。此时 dp[i] = 0 。
综上所述：dp[i] 最终的结果应该是上面四种情况下，解码成功的两种的累加和（因为我们关心的是解码方法，既然解码失败，就不用加入到最终结果中去），因此可以得到状态转移方程（dp[i] 默认初始化为 0）：
i. 当 s[i] 上的数在 [1, 9] 区间上时：dp[i] += dp[i - 1]；
ii. 当 s[i - 1] 与 s[i] 上的数结合后，在 [10, 26] 之间的时候：dp[i] += dp[i - 2] ；
如果上述两个判断都不成立，说明没有解码方法，dp[i] 就是默认值 0。
由于可能要用到 i - 1 以及 i - 2 位置上的 dp 值，因此要先初始化「前两个位置」。初始化 dp[0]：
i. 当 s[0] == '0' 时，没有编码方法，结果 dp[0] = 0 ；
ii. 当 s[0] != '0' 时，能编码成功，dp[0] = 1 初始化 dp[1]：
i. 当 s[1] 在 [1，9] 之间时，能单独编码，此时 dp[1] += dp[0]（原因同上，dp[1] 默认为 0）
ii. 当 s[0] 与 s[1] 结合后的数在 [10, 26] 之间时，说明在前两个字符中，又有一种编码方式，此时 dp[1] += 1 ；
可以在最前面加上一个辅助结点，帮助我们初始化。使用这种技巧要注意两个点：
填表顺序：
毫无疑问是「从左往右」
返回值：
应该返回 dp[n - 1] 的值，表示在 [0, n - 1] 区间上的编码方法。
C++ 算法代码： class Solution {
public :
int numDecodings (string s) int n = s.size ();
vector<int > dp (n) ;
dp[0 ] = s[0 ] != '0' ;
if (n == 1 ) return dp[0 ];
if (s[1 ] <= '9' && s[1 ] >= '1' ) dp[1 ] += dp[0 ];
int t = (s[0 ] - '0' ) * 10 + s[1 ] - '0' ;
if (t >= 10 && t <= 26 ) dp[1 ] += 1 ;
for (int i = 2 ; i < n; i++) {
if (s[i] <= '9' && s[i] >= '1' ) dp[i] += dp[i - 1 ];
int t = (s[i - 1 ] - '0' ) * 10 + s[i] - '0' ;
if (t >= 10 && t <= 26 ) dp[i] += dp[i - 2 ];
}
return dp[n - 1 ];
}
};
5. 不同路径
题目链接
解法（动态规划）： 对于这种「路径类」的问题，我们的状态表示一般有两种形式：
ii. 从起始位置出发，到达 [i, j] 位置。
dp[i][j] 表示：走到 [i, j] 位置处，一共有多少种方式。
简单分析一下。如果 dp[i][j] 表示到达 [i, j] 位置的方法数，那么到达 [i, j] 位置之前的 一小步，有两种情况：
i. 从 [i, j] 位置的上方（[i - 1, j] 的位置）向下走一步，转移到 [i, j] 位置；
ii. 从 [i, j] 位置的左方（[i, j - 1] 的位置）向右走一步，转移到 [i, j] 位置。由于我们要求的是有多少种方法，因此状态转移方程就呼之欲出了：dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 。
可以在最前面加上一个「辅助结点」，帮助我们初始化。使用这种技巧要注意两个点：
i. 辅助结点里面的值要「保证后续填表是正确的」；
在本题中，「添加一行」，并且「添加一列」后，只需将 dp[0][1] 的位置初始化为 1 即可。
根据「状态转移方程」的推导来看，填表的顺序就是「从上往下」填每一行，在填写每一行的时候「从左往右」。
根据「状态表示」，我们要返回 dp[m][n] 的值。
C++ 算法代码： class Solution {
public :
int uniquePaths (int m, int n) int >> dp (m + 1 , vector <int >(n + 1 , 0 ));
dp[0 ][1 ] = 1 ;
for (int i = 1 ; i <= m; i++) {
for (int j = 1 ; j <= n; j++) {
dp[i][j] = dp[i][j - 1 ] + dp[i - 1 ][j];
}
}
return dp[m][n];
}
};
6. 不同路径 II
题目链接
解法（动态规划）： 本题为不同路径的变型，只不过有些地方有「障碍物」，只要在「状态转移」上稍加修改就可解决。
对于这种「路径类」的问题，我们的状态表示一般有两种形式：
ii. 从起始位置出发，到达 [i, j] 位置。
dp[i][j] 表示：走到 [i, j] 位置处，一共有多少种方式。
简单分析一下。如果 dp[i][j] 表示到达 [i, j] 位置的方法数，那么到达 [i, j] 位置之前的 一小步，有两种情况：
i. 从 [i, j] 位置的上方（[i - 1, j] 的位置）向下走一步，转移到 [i, j] 位置；
ii. 从 [i, j] 位置的左方（[i, j - 1] 的位置）向右走一步，转移到 [i, j] 位置。但是，[i - 1, j] 与 [i, j - 1] 位置都是可能有障碍的，此时从上面或者左边是不可能到达 [i, j] 位置的，也就是说，此时的方法数应该是 0。
由此我们可以得出一个结论，只要这个位置上「有障碍物」，那么我们就不需要计算这个位置上的值，直接让它等于 0 即可。
可以在最前面加上一个「辅助结点」，帮助我们初始化。使用这种技巧要注意两个点：
i. 辅助结点里面的值要「保证后续填表是正确的」；
在本题中，添加一行，并且添加一列后，只需将 dp[1][0] 的位置初始化为 1 即可。
根据「状态转移」的推导，填表的顺序就是「从上往下」填每一行，每一行「从左往右」。
根据「状态表示」，我们要返回的结果是 dp[m][n]。
C++ 算法代码： class Solution {
public :
int uniquePathsWithObstacles (vector<vector<int >>& vv) int m = vv.size ();
int n = vv[0 ].size ();
vector<vector<int >> dp (m + 1 , vector <int >(n + 1 ));
dp[0 ][1 ] = 1 ;
for (int i = 1 ; i <= m; i++) {
for (int j = 1 ; j <= n; j++) {
if (vv[i - 1 ][j - 1 ] == 0 ) {
dp[i][j] = dp[i - 1 ][j] + dp[i][j - 1 ];
}
}
}
return dp[m][n];
}
};
