一维动态规划是算法入门的基础，核心在于定义状态、推导状态转移方程及初始化。本文通过泰波那契数、爬楼梯及解码方法三道经典例题，详细演示了动态规划的五个基本步骤：状态表示、状态转移、初始化、填表顺序与返回值。内容涵盖空间优化技巧如滚动数组，并针对边界条件处理提供了具体代码实现，帮助读者掌握从简单到中等难度的一维 DP 解题思路。
本章是动态规划算法的基础入门篇，通过三道简单题 + 一道中等难度的一维动态规划题带你初识动态规划，了解其基本写法。
通过大量练习可总结动态规划做题步骤。简单来说，动态规划理解为：某种状态的公式 + 提前求出来值的容器，求出当前位置的值然后放到容器中供后续使用。因为初始值通常是可见的，从而启动动态规划。
主要提炼出以下要素：
严格来说：动态规划 = 状态定义 + 状态转移方程 + 初始条件 + 状态存储（容器）
dp[i] 值的含义。
dp[i] = ?（也是最难的一步）。
dp[i] 的值到底为多少。附注：状态表示通常为'以 i 位置结尾/开头'。dp[i] 通常通过最后一个状态来进行分析。初始化通常通过第一个状态来进行分析。再做类似数字判断时，不要使用字符来简单的判断，而是将数字字符根据位数转变为真正的数字然后再进行判断。适当的需要的情况下可以开辟空间来处理边界问题。
LeetCode: 第 N 个泰波那契数
回顾五大步骤：
dp[i] 等于什么。dp[i]：第 i 个泰波那契数。dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。i-1、i-2、i-3 三个位置的值都得算好。从左向右。dp[n] 即可。class Solution {
public:
int tribonacci(int n) {
// 1. 状态表示：dp[i] = 第 i 个泰波那契序列
// 2. 状态转移方程：Tn+3 = Tn + Tn+1 + Tn+2 -> dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
vector<int> dp(n + 1);
// 3. 初始化：需要前三个，那么就是初始化 0 1 2，从 3 开始
if (n == 0) return 0;
if (n == 1 || n == 2) return 1;
dp[0] = 0; dp[1] = 1; dp[2] = 1;
// 4. 填表顺序：要求的值是 Ti，那么求就是 dp[i]，所以肯定是从小的开始，也就是从左往右
for (int i = 3; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
}
// 5. 返回值：dp[i] 即可
return dp[n];
}
int tribonacci_optimized(int n) {
// 空间优化写法
int a = 0, b = 1, c = 1;
int ret = 0;
if (n == 0) return 0;
if (n == 1 || n == 2) return 1;
for (int i = 3; i <= n; i++) {
ret = a + b + c;
a = b;
b = c;
c = ret;
}
return ret;
}
};
LeetCode: 三步问题
本题分析不难看出：要求到达某个台阶的方法（这里就能简单的看出来状态表示）。 直接拿示例一来看：如何到达台阶 n=3：
n-1、n-2、n-3。dp[n] = dp[n-1] + dp[n-2] + dp[n-3]。dp[0]=1、dp[1]=1、dp[2]=2。dp[n] 即可。dp[i] 分为三种情况：从 i-1、i-2、i-3 到达。dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。dp[0]=1, dp[1]=1, dp[2]=2。dp[n]。注意取模运算防止溢出。
class Solution {
public:
int waysToStep(int n) {
// 1. 状态表示：dp[n] 计算小孩上到 n 阶台阶有多少种上楼梯的方式
// 2. 状态方程：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
vector<int> dp(n + 3);
// 3. 初始值：同样的 0 1 2，但本题的初始化就没那么简单了
dp[0] = 1; // 到达 0 阶有几种
dp[1] = 1; // 到达 1 阶有几种
dp[2] = 2; // 到达 2 阶有几种
if (n <= 2) return dp[n];
// 4. 方向：同样需要求 i 就得先找到 i-3... 那么就得从左往右
for (int i = 3; i <= n; i++) {
dp[i] = ((long)dp[i-1] + dp[i-2] + dp[i-3]) % 1000000007;
}
// 5. 返回 dp[n] 即可
return dp[n];
}
int waysToStep_optimized(int n) {
// 空间优化写法
if (n == 1 || n == 2) return n;
if (n == 3) return 4;
int dp1 = 1, dp2 = 2, dp3 = 4, dp4;
for (int i = 4; i <= n; ++i) {
dp4 = ((dp1 + dp2) % 1000000007 + dp3) % 1000000007;
dp1 = dp2;
dp2 = dp3;
dp3 = dp4;
}
return dp4;
}
};
LeetCode: 使用最小花费爬楼梯
楼顶在最后。
解法一：
dp[i] 表示：到达 i 位置时，最小花费。i-1，然后支付 cost[i-1]，走一步：dp[i-1] + cost[i-1]。i-2，然后支付 cost[i-2]，走两步：dp[i-2] + cost[i-2]。dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])。dp[0] = 0, dp[1] = 0（0 1 台阶是 0 元，所以直接从 2 开始即可）。dp[n]。解法二：
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] + cost[i], dp[i+2] + cost[i])。dp[n-1] = cost[n-1], dp[n-2] = cost[n-2]。min(dp[0], dp[1])。class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
// cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用
// 爬到楼顶本质就是超过容器个数 size=3 就需要爬到 4（下标 3）
int n = cost.size();
vector<int> dp(n + 1);
// 2. 状态转移方程：dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
// 3. 初始化：最小情况：dp[2] = min(dp[1], dp[0]) + cost[2]，故初始化 dp[1] dp[2] 即可
dp[0] = 0;
dp[1] = 0;
for (int i = 2; i <= n; i++) {
dp[i] = min(dp[i-1], dp[i-2]) + cost[i-1];
}
return dp[n];
}
};
通过上述三道题，估计你对动态规划中的最基本的步骤和思想都有一定的认识了，下面就不将是简单的套公式了，而是结合一些内容进一步深化对动态规划的理解。
LeetCode: 解码方法
本题如何想到的呢：从最后一个节点来看，不难发现规律。
dp[i] 单独解码（1 ~ 9）：解码成功（个数为 dp[i-1]），失败则为 0。dp[i] 与 dp[i-1] 结合解码（10 ~ 26）：解码成功（dp[i-2]），失败则为 0。dp[0]、dp[1]。dp[n-1]，n-1 最后一个位置。整个数组多开一位，然后通过使用这个多开的一位虚拟节点的初始化来帮助运算。 注意事项：
dp[1] 时使用的 dp[i-2]，所以填 1（因为前面也没字符判断了，所以填 1 给到 dp[2]，代表正确）。s[i-1]。class Solution {
public:
int numDecodings(string s) {
// dp[i]: 以 i 位置结尾的解码个数
// dp[i] = dp[i-1] + dp[i-2]，其中若不能解码则不进行相加，或者加 0
// 初始化：因为 s.length >= 1，所以需要一个多的空位，来特殊处理等于 1 的情况
int n = s.size();
vector<int> dp(n + 2);
// 结果存在 n 下标
dp[0] = 1; // 默认解码个数为 1 次
dp[1] = 1; // 默认解码个数为 1 次
if (s[0] == '0') return 0;
for (int i = 0; i < n; i++) {
// 单个字符判断
int val = s[i] - '0';
if (val >= 1 && val <= 9) dp[i + 2] += dp[i + 1];
// 两个字符判断
int combine = i - 1 >= 0 ? (s[i - 1] - '0') * 10 + val : -1;
if (combine >= 10 && combine <= 26) dp[i + 2] += dp[i];
}
return dp[n + 1];
}
};
对于需要判断两位或者多位数字时，不要图方便使用字符判断，而是将他转换为数字。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online