蓝桥杯 Java B 组之简单动态规划（爬楼梯、斐波那契数列）

Day 6：简单动态规划（爬楼梯、斐波那契数列）

动态规划（Dynamic Programming，简称 DP）是计算机科学中的一种算法设计思想，用来解决最优解问题，它的核心思想是将大问题分解为小问题，并通过保存计算结果避免重复计算。常见的应用场景包括：最短路径、最优子结构、背包问题等。

今天，我们将详细学习两个经典的动态规划问题：

• 爬楼梯问题
• 斐波那契数列

 一、动态规划概念

动态规划适用于能够分解为子问题的问题，并且子问题的解可以保存并复用。动态规划通过状态转移方程来计算最优解。

通俗理解：动态规划就像“做笔记”——把重复计算的结果记录下来，避免重复劳动。

核心思想：将大问题拆解为小问题，通过解决小问题逐步解决大问题，并保存中间结果（称为“状态”）。

1. 状态转移方程：

• 状态转移方程是用来描述从一个状态到另一个状态的关系。
• 通过状态转移方程，可以一步步得到最终的最优解。

---

 二、爬楼梯问题

问题描述：

假设你正在爬楼梯，楼梯有 n 阶，每次可以爬 1 阶或 2 阶。你有多少种方法可以爬到楼顶？

思路分析：

• 对于楼梯的第 n 阶，你可以从第 n-1 阶跳一步，或者从第 n-2 阶跳两步。
• 所以，到达第 n 阶的方法数等于到达第 n-1 阶和第 n-2 阶的方法数之和。

状态转移方程：

f(n)=f(n−1)+f(n−2)f(n) = f(n-1) + f(n-2)

• f(n) 表示到达第 n 阶的总方法数。
• 初始条件：
  • f(0) = 1（没有阶梯时有一种“爬”的方法，就是不动）
  • f(1) = 1（只有一阶时，只有一种爬法）

代码实现：

public class ClimbingStairs {public static int climbStairs(int n) {if (n == 0) return 0;  // 没有楼梯的情况if (n == 1) return 1;  // 只有一阶的情况int first = 1;  // f(1) = 1int second = 2; // f(2) = 2int result = 0;for (int i = 3; i <= n; i++) {result = first + second;  // f(n) = f(n-1) + f(n-2)first = second;           // 更新 f(n-1)second = result;          // 更新 f(n-2)}return result;}public static void main(String[] args) {int n = 5;  // 假设楼梯有 5 阶System.out.println(climbStairs(n));  // 输出结果}}

• 解释：
  • 初始化 first = 1 和 second = 2，分别表示到达第 1 阶和第 2 阶的方法数。
  • 通过循环从第 3 阶开始，根据状态转移方程 f(n) = f(n-1) + f(n-2) 计算到达每一阶的方法数，最终返回到达第 n 阶的总方法数。

时间复杂度： O(n)

空间复杂度： O(1)

这个解法通过空间优化，只用常数空间来存储前两个状态，因此是最优解。

---

 三、斐波那契数列（Fibonacci Sequence）

问题描述：

斐波那契数列是一个经典的数列，定义如下：

f(0)=0f(1)=1f(n)=f(n−1)+f(n−2),n>=2f(0) = 0 f(1) = 1 f(n) = f(n-1) + f(n-2), n >= 2

即数列的前两个数字是 0 和 1，从第三项开始，每一项是前两项之和。计算第 n 项。

思路分析：

• 斐波那契数列和爬楼梯问题是同一种类型的问题。
• 第 n 项的数值是前两项之和，符合动态规划的最优子结构。

状态转移方程：

f(n)=f(n−1)+f(n−2)f(n) = f(n-1) + f(n-2)

代码实现（递归）：

public class Fibonacci {// 递归实现public static int fib(int n) {if (n == 0) return 0;if (n == 1) return 1;return fib(n - 1) + fib(n - 2);  // 递归调用}public static void main(String[] args) {int n = 6;  // 求斐波那契数列的第 6 项System.out.println(fib(n));  // 输出结果}}

• 解释： 
  • 基本的递归实现，计算第 n 项的数值。
  • 递归的时间复杂度是 O(2^n)，因为每个递归会产生两个子问题，计算速度较慢。

改进：动态规划实现（记忆化递归）

public class FibonacciDP {public static int fib(int n) {int[] dp = new int[n + 1];dp[0] = 0;  // f(0) = 0dp[1] = 1;  // f(1) = 1for (int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];  // 状态转移方程}return dp[n];}public static void main(String[] args) {int n = 6;  // 求斐波那契数列的第 6 项System.out.println(fib(n));  // 输出结果}}

• 解释： 
  • 使用 动态规划 数组 dp 来存储中间结果，避免重复计算。
  • 时间复杂度是 O(n)，空间复杂度是 O(n)。
  • 为什么使用n + 1：
  • 索引从0开始：在Java中，数组的索引是从0开始的。因此，如果我们想要存储从第1项到第n项的解，我们需要一个长度为n + 1的数组，这样索引范围就是从0到n。
  • 方便访问：使用n + 1的数组，我们可以直接使用dp[i]来访问第i项的解，而不需要进行额外的索引转换。

优化：空间复杂度 O(1)

public class FibonacciOptimized {public static int fib(int n) {if (n == 0) return 0;if (n == 1) return 1;int first = 0, second = 1;  // f(0) = 0, f(1) = 1int result = 0;for (int i = 2; i <= n; i++) {result = first + second;first = second;second = result;}return result;}public static void main(String[] args) {int n = 6;  // 求斐波那契数列的第 6 项System.out.println(fib(n));  // 输出结果}}

• 解释： 
  • 通过空间优化，只用两个变量 first 和 second 存储前两个斐波那契数值，减少了空间复杂度。
  • 时间复杂度是 O(n)，空间复杂度是 O(1)。

总结：

• 递归法： 直接递归实现，虽然简单，但由于大量重复计算，效率低。
• 动态规划（DP）： 通过存储中间计算结果，避免重复计算，显著提高效率。
• 空间优化： 动态规划可以通过滚动数组技巧来优化空间复杂度。

时间复杂度： O(n)

空间复杂度： O(1)（优化后的解法）

---

四、常考点总结

知识点	内容	常见问题
状态转移方程	动态规划的核心是递推关系（例如：f(n) = f(n-1) + f(n-2)）	题目能否用动态规划解决，是否存在最优子结构？
爬楼梯问题	动态规划解法，关键是通过状态转移方程f(n) = f(n-1) + f(n-2)来计算	边界条件的处理，空间优化的使用
**斐波那契

动态规划解题步骤总结

定义状态：明确dp[i]表示什么（如斐波那契数、爬楼梯方法数）。

建立状态转移方程：找到dp[i]与dp[i-1]、dp[i-2]等的关系。

初始化：设置初始值（如dp[0]、dp[1]）。

确定计算顺序：通常从前往后遍历。

空间优化：用变量代替数组（如滚动数组）。

常考题型

基础DP问题：斐波那契、爬楼梯、路径计数。

变种DP问题：最小路径和、背包问题简化版。

二维DP问题：网格中的动态规划（如机器人路径）。

动态规划的两个主要特征：

重叠子问题：问题可以分解为多个子问题，这些子问题不是独立的，而是相互重叠的。

最优子结构：问题的最优解包含其子问题的最优解。

爬楼梯问题

爬楼梯问题是一个经典的动态规划问题。假设你正在爬楼梯，每次可以爬1阶或2阶，问到达第n阶楼梯有多少种不同的方法。

解题思路：

状态定义：设dp[i]表示到达第i阶楼梯的方法数。

状态转移方程：dp[i] = dp[i-1] + dp[i-2]，即到达第i阶的方法数等于到达第i-1阶和第i-2阶的方法数之和。

初始条件：dp[1] = 1（到达第1阶只有1种方法），dp[2] = 2（到达第2阶有2种方法：1+1或2