蓝桥杯JavaB组之总结与模拟题练习

蓝桥杯 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) = 0         if (n == 1) return 1;  // f(1) = 1                  int first = 0;  // f(0) = 0         int second = 1; // f(1) = 1         int 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)，需要灵活运用滚动数组等技巧。

---