什么是动态规划？
动态规划（Dynamic Programming，简称 DP）是一种解决复杂问题的算法设计方法，其核心思想是将原问题拆解成相对简单的子问题，逐个解决并保存子问题的结果，避免重复计算，从而高效地求解问题。
动态规划适合具有以下两个性质的问题：重叠子问题（Overlapping Subproblems）：子问题会重复出现；最优子结构（Optimal Substructure）：原问题的最优解包含子问题的最优解。
简单理解就是'记住求过的解，避免重复计算'，比如经典的斐波那契数列就是动态规划的入门例子。
核心思想
- 拆分子问题：将大问题拆成子问题。
- 保存历史结果：用数组、哈希表等结构缓存已经算过的子问题结果。
- 避免重复计算：子问题只计算一次，节省时间。
举个例子：
计算
1+1+1+1+1+1+1+1的值是 8，如果我在这个基础上再加一个1，结果就是 9，不用重新计算整个加法过程，直接利用之前的结果。
这就是动态规划节省计算的精髓。
例子 1 — 青蛙跳台阶问题
题目描述： 一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级台阶。求跳上 10 级台阶的跳法总数。
1. 暴力递归解法（超时示范）
定义 f(n) 表示跳到第 n 级台阶的跳法数。根据题意：
f(n) = f(n-1) + f(n-2)
边界条件：
f(1) = 1
f(2) = 2
代码实现：
int numWays(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return numWays(n - 1) + numWays(n - 2);
}
