动态规划基础
动态规划(Dynamic Programming)的核心在于将复杂问题分解为重叠子问题,并通过存储中间结果避免重复计算。简单来说,它包含四个要素:状态定义、状态转移方程、初始条件以及状态存储(通常用数组或容器实现)。
在解决具体题目时,我们可以遵循以下思路:
- 状态表示:明确 dp[i] 的含义,例如'以 i 结尾的最大值'或'到达 i 位置的方法数'。
- 状态转移:推导 dp[i] 与之前状态的关系,这是最关键的一步。
- 初始化:处理边界情况,确保填表过程不越界。
- 填表顺序:根据依赖关系决定遍历方向,通常是从左到右或从下到上。
- 返回值:根据题意从 dp 表中提取最终结果。
下面通过四道经典例题,逐步演示如何应用这些步骤。
1. 第 N 个泰波那契数
这道题是典型的线性递推问题。泰波那契数列定义为 T(n) = T(n-1) + T(n-2) + T(n-3),初始值为 T(0)=0, T(1)=1, T(2)=1。
解题思路: 直接观察公式即可得到状态转移方程。由于计算 T(i) 只需要前三个值,我们可以使用滚动数组优化空间复杂度,无需维护整个 dp 数组。
代码实现:
class Solution {
public:
int tribonacci(int n) {
// 空间优化写法:使用三个变量代替 dp 数组
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;
}
};
2. 三步问题
假设小孩每次可以走 1、2 或 3 步,求到达第 n 阶台阶有多少种方法。
分析: 要到达第 i 阶,最后一步可能来自 i-1、i-2 或 i-3。因此,dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。这与泰波那契数类似,但需要注意取模运算以防止整数溢出。


