1. 什么是动态规划
动态规划是一种通过将复杂问题分解为重叠子问题，并利用子问题的解来高效求解原问题的算法思想。它的核心是避免重复计算，通过存储中间结果（即'记忆化'）来优化时间复杂度。
简单来说，就是通过前面的状态来定义后面的状态。例如前缀和问题也可视为一种简单的动态规划，通常归类于基础算法中。
2. 动态规划步骤
做动态规划类题目的步骤如下：
状态表示
状态表示就是数组对应位置值的含义，即该值代表什么。例如前缀和的状态表示就是原数组前面这些数的累加。
状态转移方程
状态转移方程是根据状态表示得到的公式。例如前缀和的状态转移方程为 dp[i] = dp[i-1] + nums[i]。
初始化
初始化的作用是防止数组越界访问，提前给 DP 表的一小部分值赋值，方便后续计算。例如前缀和中第 0 个位置直接设为 0。
填表顺序
填表顺序需确保计算当前位置的值时，所需的前置值已经计算完成。
返回值
返回值即题目要求的结果。
3. 例题讲解及具体代码
3.1 LeetCode 1137. 第 N 个泰波那契数
题目要求当前位置的值由前面三个位置的值决定。
- 状态表示：当前位置值等于前面三个位置的值的和。
- 状态转移方程：
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。 - 初始化：第 0 个位置设为 0，第 1、2 个位置设为 1。
- 填表顺序：从前往后。
- 返回值：第 n 个位置的值。
基于上述步骤，代码实现如下：
class Solution {
public:
int tribonacci(int n) {
if (n == 0) return 0;
if (n == 1 || n == 2) return 1;
vector<int> dp(n + 1);
dp[0] = 0;
dp[1] = 1;
dp[2] = 1;
for (int i = 3; i <= n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
}
return dp[n];
}
};
3.2 面试题 08.01. 三步问题
题目要求计算小孩走到第 n 步的方法数。
- 状态表示：
dp[n]表示走到当前位置时的方法数。 - 状态转移方程：由于每次可以走 1、2 或 3 步，到达当前位置的方法数等于前三个位置方法数之和。注意不要重复计算，只需累加前三个位置的方法数即可。
- 初始化：到第 1 步有 1 种办法，第 2 步有 2 种，第 3 步有 4 种。
- 填表顺序：从前向后。
- 返回值：第 n 位置的方法数。
明确上述要素后，即可编写代码。注意在加法过程中取模以防止溢出。
class Solution {
public:
int waysToStep(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
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]) % 1000000007 + dp[i - 3]) % 1000000007;
}
return dp[n];
}
};
