蓝桥杯 Java B 组 - 第七天：周总结与模拟题练习
Day 7：周总结与模拟题练习
在这一周的学习中，我们已经接触了动态规划的基本概念和常见应用。今天，我们将通过刷一些蓝桥杯的模拟题，来熟悉并巩固所学的知识，特别是动态规划的问题。
一、模拟题：Fibonacci数列求余
题目描述：
给定正整数 n，求斐波那契数列的第 n 项，并计算其对一个数 m 的余数。即：
f(n)f(n) % m
例如：
- 输入 n=10，m=100
- 输出：f(10) % 100 的结果。
解题思路：
斐波那契数列：斐波那契数列是一个经典的递归问题，其递推关系是：
- f(n)=f(n−1)+f(n−2)f(n) = f(n-1) + f(n-2)
其中，f(0) = 0，f(1) = 1。
需要注意的是，题目要求计算 f(n) % m，而不直接求 f(n)。所以在计算每个斐波那契数时，我们可以提前取余，这样可以防止数值过大，避免溢出。
代码实现：
public class FibonacciModulo {// 求斐波那契数列第n项对m取余public static int fibonacciModulo(int n, int m) {if (n == 0) return 0; // f(0) = 0if (n == 1) return 1; // f(1) = 1int first = 0; // f(0) = 0int second = 1; // f(1) = 1int result = 0;for (int i = 2; i <= n; i++) {// 计算下一项，先对m取余，防止结果溢出result = (first + second) % m;first = second;second = result;}return result;}public static void main(String[] args) {int n = 10; // 第10项int m = 100; // 对100取余System.out.println(fibonacciModulo(n, m)); // 输出结果}}解释：
- 核心思想：每次计算当前斐波那契数时，都取其与 m 的余数，以防止数字过大。
- 时间复杂度：O(n)，因为我们从第 2 项开始依次计算到第 n 项。
- 空间复杂度：O(1)，仅使用了常数的额外空间。
二、模拟题：数字三角形
题目描述：
给定一个数字三角形，要求从三角形的顶部到达底部的路径，使得路径上的数字和最大。每次可以从当前数字向下一行的两个相邻数字之一移动，求最大路径和。
例如：
3
7 4
2 4 6
8 5 9 3
从顶部的 3 开始，可以选择路径 3 -> 7 -> 4 -> 6 -> 9，路径和为 29。
解题思路：
这个问题可以用动态规划（DP）来解决：
- 从底部开始，逐步向上计算每一层的最大路径和。
- 对于每一个数字，它的路径和等于它本身的值加上下面两行相邻数字的最大路径和。
状态转移方程：
对于三角形中任意位置 (i, j)，其路径和为：
dp(i,j)=max(dp(i+1,j),dp(i+1,j+1))+triangle(i,j)dp(i, j) = max(dp(i+1, j), dp(i+1, j+1)) + triangle(i, j)
其中 dp(i, j) 表示从位置 (i, j) 到达底部的最大路径和。
代码实现：
public class TrianglePathSum {public static int maximumTotal(int[][] triangle) {int n = triangle.length; // 获取三角形的高度// 从倒数第二行开始向上计算for (int row = n - 2; row >= 0; row--) { for (int col = 0; col <= row; col++) {// 状态转移：当前元素加上其下面两个元素中的最大者triangle[row][col] += Math.max(triangle[row + 1][col], triangle[row + 1][col + 1]);}}// 返回三角形顶点的最大路径和return triangle[0][0];}public static void main(String[] args) {int[][] triangle = {{3},{7, 4},{2, 4, 6},{8, 5, 9, 3}};System.out.println(maximumTotal(triangle)); // 输出最大路径和}}解释：
- 核心思想：我们从三角形的倒数第二行开始，逐行计算每个元素的最大路径和，直到顶部。
- 时间复杂度：O(n^2)，因为三角形共有 n 行，每行最多 n 个元素。
- 空间复杂度：O(1)，我们直接修改原三角形数组，空间复杂度为常数。
三、其他常见题型和技巧
1. 背包问题（Knapsack Problem）
- 0/1背包问题：给定物品的重量和价值，以及背包的最大承重，求能够装入背包的最大价值。使用动态规划来求解。
- 完全背包问题：每个物品可以无限多次放入背包，使用动态规划来计算最大价值。
2. 子序列问题
- 最长递增子序列（LIS）：给定一个整数数组，求其中最长递增子序列的长度。动态规划解法，通过维护一个 dp 数组。
- 最长公共子序列（LCS）：给定两个字符串，求它们的最长公共子序列。
3. 区间问题
- 区间最大和：给定一个整数数组，求其中一个连续区间的最大和。常见的解法是使用动态规划，利用 Kadane 算法。
4. 最短路径问题
- Dijkstra算法：用于计算一个图中从起点到其他所有点的最短路径。
- Bellman-Ford算法：用于计算一个图中从起点到所有其他点的最短路径，并且可以处理负权边。
四、总结与易错点
1. 动态规划（DP）常见问题：
- 边界条件：动态规划中的边界条件设置很重要，尤其是在处理递归或递推时要特别注意。例如，在计算斐波那契数列时，f(0) = 0 和 f(1) = 1。
- 状态转移方程：一定要搞清楚如何从子问题推导出当前问题的解，这通常是动态规划能否成功的关键。
2. 常见易错点：
- 递归求解中重复计算：在递归中，如果没有优化，可能会进行大量重复的计算。使用动态规划来保存已经计算过的结果可以大大减少计算量。
- 忘记对结果取余：在解决类似 Fibonacci 数列求余的问题时，记得每一步计算都要取余，否则可能会出现数值过大导致溢出。
3. 动态规划常见误区：
- 不理解状态转移方程：很多题目要求写出状态转移方程，但如果没有充分理解题目的结构，可能很难准确地表达出方程。建议做更多的练习来熟悉这类问题的解法。
- 空间复杂度过高：有些动态规划题目可以通过空间优化将空间复杂度降到 O(1)，需要灵活运用滚动数组等技巧。
