C++算法
C++ 算法入门：一维动态规划基础实战
一维动态规划通过状态定义、状态转移方程、初始化和填表顺序解决问题。文章结合第 N 个泰波那契数、三步问题、最小花费爬楼梯及解码方法四道例题，详解了动规的基本步骤与空间优化技巧，涵盖边界处理与虚拟节点用法，帮助读者掌握一维动规实战思路。
一维动态规划通过状态定义、状态转移方程、初始化和填表顺序解决问题。文章结合第 N 个泰波那契数、三步问题、最小花费爬楼梯及解码方法四道例题，详解了动规的基本步骤与空间优化技巧，涵盖边界处理与虚拟节点用法，帮助读者掌握一维动规实战思路。
通过大量练习总结出的动态规划做题步骤，可以理解为：某种状态的公式 + 提前求出来值的容器，求出当前位置的值然后放到容器中供后续使用。因为最开始的值一般是可见的，所以能确定初始值，从而启动动态规划。
主要提炼出以下要素：
严格来说：动态规划 = 状态定义 + 状态转移方程 + 初始条件 + 状态存储（容器）
dp[i] 值的含义。
dp[i] = ?（也是最难的一步）。
dp[i] 的值。提示：状态表示通常为'以 i 位置结尾/开头'。初始化通常通过第一个状态进行分析。做类似数字判断时，不要使用字符来简单的判断，而是将数字字符根据位数转变为真正的数字然后再进行判断。适当的需要的情况下可以开辟空间来处理边界问题。
回顾五大步骤：
dp[i] 表示第 i 个泰波那契数。dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。dp[n]。空间优化：当我们在填某个表，某个状态只需要前面的若干个状态时，就可以使用滚动数组进行优化。本题仅需要某个数的前 3 个即可，可以用 3 个变量 abc 来标明前 3 个数。
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); // 提前开辟好 n 个位置的空间，注意从0开始所以+1
// 3. 初始化：需要前三个 那么就是初始化 0 1 2，从3开始
if (n >= 0) dp[0] = 0;
if (n >= 1) dp[1] = 1;
if (n >= 2) 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 tribonacciOptimized(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;
}
};
问题分析：要求到达某个台阶的方法（状态表示）。
dp[n] = dp[n-1] + dp[n-2] + dp[n-3]。dp[0]：走到 0，不用走，为 1。dp[1]：走到 1，只能从 0 走一步，为 1。dp[2]：走到 2，能从 0 走 2 步和从 1 走 1 步，为 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];
}
// 写法二：忽略 0 台阶直接从 1 开始
int waysToStepV2(int n) {
vector<int> dp(n + 3);
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
for (int i = 4; i <= n; i++) {
dp[i] = ((long)dp[i - 1] + dp[i - 2] + dp[i - 3]) % 1000000007;
}
return dp[n];
}
// 写法三：空间优化
int waysToStepOptimized(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;
}
};
楼顶在最后。
解法一：
dp[i] 表示到达 i 位置时的最小花费。dp[i-1] + cost[i-1]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 元，或者根据具体逻辑调整，此处按常见 LeetCode 逻辑，cost 数组长度为 n，爬到楼顶即超过 size）。
dp[i] 表示到达第 i 层需要的最小花费。dp[0]=cost[0], dp[1]=cost[1]。dp[n]。解法二：
dp[i] 表示从 i 位置开始，到达楼顶的最小花费。dp[i+1] + cost[i]dp[i+2] + cost[i]dp[i] = min(dp[i+1] + cost[i], dp[i+2] + cost[i])min(dp[0], dp[1])。class Solution {
public:
// 解法一：从前向后
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int> dp(n + 1);
// 初始化：最小情况：dp[2] = min(dp[1], dp[0]) + cost[2]，故初始化 dp[1] dp[2] 即可
// 实际上 dp[0] 和 dp[1] 代表到达第 0 阶和第 1 阶的花费，通常可以直接踩上去，费用为 0 或者 cost[0/1]
// 根据题目描述，踏上台阶需要支付 cost[i]，所以 dp[i] 表示到达 i 位置并支付该位置费用的最小总花费
// 另一种理解：dp[i] 表示到达 i 位置所需的最小花费（不包含 i 的费用），则最后一步是 min(dp[n-1]+cost[n-1], dp[n-2]+cost[n-2])
// 此处采用常见解法：dp[i] 表示到达第 i 阶台阶的最小花费
dp[0] = 0;
dp[1] = 0;
for (int i = 2; i <= n; i++) {
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[n];
}
// 解法二：从后向前
int minCostClimbingStairsV2(vector<int>& cost) {
int n = cost.size();
vector<int> dp(n + 1);
dp[n] = 0;
dp[n - 1] = cost[n - 1];
for (int i = n - 2; i >= 0; i--) {
dp[i] = cost[i] + min(dp[i + 1], dp[i + 2]);
}
return min(dp[0], dp[1]);
}
};
通过上述几道题不难总结出常用的状态表示经验：
本质也就是：状态表示不简单了、状态方程也没那么好推导了。需要在抽象的题目中提炼出动态规划。
本题如何想到的呢：从最后一个节点来看，不难发现规律。
dp[i] += dp[i-1]dp[i] += dp[i-2]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]。整个数组多开一位，然后通过使用这个多开的一位虚拟节点的初始化来帮助运算。
dp[1] 时使用的 dp[i-2]，需要填 1（代表正确）。class Solution {
public:
int numDecodings(string s) {
int dp[101] = {};
// 初始化 0 和 1
dp[0] = 1; // 虚拟节点
if (s.length() > 0 && s[0] != '0') dp[1] = 1;
for (int i = 2; i <= s.size(); i++) {
// 单个字符
int onechar = s[i - 1] - '0';
if (onechar >= 1 && onechar <= 9) {
dp[i] += dp[i - 1];
}
// 两个字符
int combine = (s[i - 2] - '0') * 10 + onechar;
if (combine >= 10 && combine <= 26) {
dp[i] += dp[i - 2];
}
if (dp[i] == 0) return 0;
}
return dp[s.size()];
}
// 解法二：使用 vector
int numDecodingsV2(string s) {
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