本文档总结了在C++编程中解决动态规划问题的关键技巧和常用方法，涵盖从基础概念到复杂应用案例的全面解析。
### C++ 动态规划问题汇总
#### 一、引言
动态规划（Dynamic Programming，简称 DP）是一种解决多阶段决策过程最优化问题的方法。它适用于具有重叠子问题和最优子结构特性的问题。本篇文章主要针对一些经典的动态规划题目进行归纳总结，并给出了解决方案和思路。
#### 二、动态规划基础知识回顾
在深入分析题目之前，先简要回顾一下动态规划的基本概念：
- **状态定义**：确定动态规划问题中的状态变量。
- **状态转移方程**：定义如何从一个状态转移到另一个状态。
- **边界条件**：定义初始状态或特殊情况下的值。
- **方向求解**：通常有自底向上（迭代）和自顶向下（递归 + 记忆化）两种方式。
#### 三、具体题目解析
##### 1. 爬楼梯的最少成本
**题目描述**：给定一个非负整数数组 `cost`，其中 `cost[i]` 表示第 `i` 个阶梯的体力花费值。目标是从起点到达顶层的最小花费。可以选择从第 0 或第 1 个阶梯开始。
**解题思路**：
- **状态定义**：`dp[i]` 表示到达第 `i` 个阶梯所需的最小花费。
- **状态转移方程**：`dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])`。
- **边界条件**：`dp[0] = cost[0]`, `dp[1] = cost[1]`。
- **最终结果**：返回 `min(dp[n-1], dp[n-2])`。
**代码实现**：
```cpp
class Solution {
public:
int minCostClimbingStairs(vector& cost) {
vector dp(cost.size() + 1);
dp[0] = cost[0];
dp[1] = cost[1];
for (int i = 2; i < cost.size() + 1; i++) {
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return min(dp[cost.size()], dp[cost.size() - 1]);
}
};
```
---
##### 2. 粉刷房子
**题目描述**：给定一个 `n x 3` 的二维数组 `costs`，其中 `costs[i][j]` 表示粉刷第 `i` 个房子为颜色 `j` 的花费。目标是最小化粉刷所有房子的总成本，且相邻房子颜色不同。
**解题思路**：
- **状态定义**：`dp[i][j]` 表示粉刷到第 `i` 个房子并将其涂成颜色 `j` 的最小成本。
- **状态转移方程**：`dp[i][j] = costs[i][j] + min(dp[i-1][k])` 其中 `k ≠ j`。
- **边界条件**：`dp[0]` 直接等于 `costs[0]`。
- **最终结果**：返回 `min(dp[n-1][0], dp[n-1][1], dp[n-1][2])`。
**代码实现**：
```cpp
class Solution {
public:
int minCost(vector>& costs) {
int m = costs.size();
int n = m == 0 ? 0 : costs[0].size();
vector> dp(m, vector(n));
dp[0] = costs[0];
for (int i = 1; i < m; i++) {
for (int j = 0; j < n; j++) {
int tempMin = INT_MAX;
for (int k = 0; k < n; k++) {
if (k != j) {
tempMin = min(tempMin, dp[i - 1][k]);
}
}
dp[i][j] = costs[i][j] + tempMin;
}
}
return *min_element(dp.back().begin(), dp.back().end());
}
};
```
---
##### 3. 翻转字符
**题目描述**：给定一个由 `0` 和 `1` 组成的字符串 `s`，目标是通过最少次数的翻转操作使得字符串变成“单调递增”的形式，即所有的 `0` 在 `1` 的前面。
**解题思路**：
- **状态定义**：`dp[i][0]` 表示前 `i` 个字符翻转 `0` 成 `1` 的最小翻转次数；`dp[i][1]` 表示前 `i`
5星
