简单动态规划（DP）讲解

动态规划是一种通过将复杂问题分解为更简单的子问题来解决问题的方法。它特别适用于有重叠子问题和最优子结构的问题。

动态规划的基本思想

1. 分解问题：将一个复杂问题分解成若干个子问题
2. 记忆化：存储子问题的解，避免重复计算
3. 自底向上：从最基本的子问题开始解决，逐步构建更复杂问题的解

动态规划的关键要素

1. 状态定义：明确定义子问题，通常用dp[i]或dp[i][j]表示
2. 状态转移方程：描述子问题之间的关系
3. 初始条件：最基本子问题的解
4. 计算顺序：通常是自底向上

爬楼梯问题详解

让我们通过这个爬楼梯问题来详细理解DP：

1. 问题理解

• 飞飞要爬n层楼
• 每次可以爬1层或2层
• 求有多少种不同的爬楼方式

2. 状态定义

我们定义dp[i]表示爬到第i层楼的不同方案数。

3. 状态转移方程

思考：要到达第i层楼，最后一步可能是从哪里来的？

• 可能是从第(i-1)层爬1层到达
• 可能是从第(i-2)层爬2层到达

所以，到达第i层的总方案数 = 到达第(i-1)层的方案数 + 到达第(i-2)层的方案数

即：dp[i] = dp[i-1] + dp[i-2]

4. 初始条件

• dp[1] = 1：爬到第1层只有一种方式（爬1层）
• dp[2] = 2：爬到第2层有两种方式（爬1层两次，或直接爬2层）

5. 详细计算过程（以n=5为例）

1. 初始化：

   • dp[1] = 1
   • dp[2] = 2

2. 计算dp[3]：

   • dp[3] = dp[2] + dp[1] = 2 + 1 = 3
   • 意思是：爬到第3层有3种方式
     • 方式1：1层+1层+1层
     • 方式2：1层+2层
     • 方式3：2层+1层

3. 计算dp[4]：

   • dp[4] = dp[3] + dp[2] = 3 + 2 = 5
   • 意思是：爬到第4层有5种方式
     • 从第3层爬1层到达（3种）
     • 从第2层爬2层到达（2种）

4. 计算dp[5]：

   • dp[5] = dp[4] + dp[3] = 5 + 3 = 8
   • 意思是：爬到第5层有8种方式
     • 从第4层爬1层到达（5种）
     • 从第3层爬2层到达（3种）

6. 完整代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int main() {
	LL n, dp[20];
	cin >> n;
	dp[1] = 1;
	dp[2] = 2;
	for (LL i = 3; i <= n; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	cout << dp[n];
	
	return 0;
} 

动态规划的优势

1. 避免重复计算：通过存储子问题的解，避免了递归中的重复计算
2. 高效性：通常比递归更高效
3. 适用性广：可以解决许多复杂问题

如何识别DP问题

1. 问题要求最优解（最大值、最小值等）或计数
2. 问题可以分解为相互依赖的子问题
3. 子问题的解可以被重复使用