蓝桥杯 Java B 组之总结与模拟题训练

 蓝桥杯 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)。所以在计算每个斐波那契数时，我们可以提前取余，这样可以防止数值过大，制止溢出。

• 
  

代码实现：

1. public class FibonacciModulo {
3.     // 求斐波那契数列第n项对m取余
5.     public static int fibonacciModulo(int n, int m) {
7.         if (n == 0) return 0;  // f(0) = 0
9.         if (n == 1) return 1;  // f(1) = 1
11.         
13.         int first = 0;  // f(0) = 0
15.         int second = 1; // f(1) = 1
17.         int result = 0;
19.         
21.         for (int i = 2; i <= n; i++) {
23.             // 计算下一项，先对m取余，防止结果溢出
25.             result = (first + second) % m;
27.             first = second;
29.             second = result;
31.         }
33.         
35.         return result;
37.     }
41.     public static void main(String[] args) {
43.         int n = 10;  // 第10项
45.         int m = 100; // 对100取余
47.         System.out.println(fibonacciModulo(n, m));  // 输出结果
49.     }
51. }

复制代码

表明：

• 焦点头脑：每次计算当前斐波那契数时，都取其与 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) 到达底部的最大路径和。

代码实现：

1. public class TrianglePathSum {
3.     public static int maximumTotal(int[][] triangle) {
5.         int n = triangle.length;  // 获取三角形的高度
7.         
9.         // 从倒数第二行开始向上计算
11.         for (int row = n - 2; row >= 0; row--) {  
13.             for (int col = 0; col <= row; col++) {
15.                 // 状态转移：当前元素加上其下面两个元素中的最大者
17.                 triangle[row][col] += Math.max(triangle[row + 1][col], triangle[row + 1][col + 1]);
19.             }
21.         }
23.         
25.         // 返回三角形顶点的最大路径和
27.         return triangle[0][0];
29.     }
33.     public static void main(String[] args) {
35.         int[][] triangle = {
37.             {3},
39.             {7, 4},
41.             {2, 4, 6},
43.             {8, 5, 9, 3}
45.         };
47.         System.out.println(maximumTotal(triangle));  // 输出最大路径和
49.     }
51. }

复制代码

表明：

• 焦点头脑：我们从三角形的倒数第二行开始，逐行计算每个元素的最大路径和，直到顶部。
  
• 时间复杂度：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)，需要机动运用滚动数组等本领。
  

---

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。