什么是动态规划?
动态规划(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);
}


