虚拟机iis网站建设,益阳网站建设,中国采购网,震旦网站谁做的#x1f353;系列专栏:蓝桥杯 #x1f349;个人主页:个人主页 目录 1.最大连续子段和
2.LCS 最大公共子序列
3.LIS 最长上升子序列
4.数塔
5.最大子矩阵和
6.背包问题
①01背包问题
②完全背包 1.最大连续子段和
这段代码是一个求最大子数组和的算法#xff0c;使用… 系列专栏:蓝桥杯 个人主页:个人主页 目录 1.最大连续子段和
2.LCS 最大公共子序列
3.LIS 最长上升子序列
4.数塔
5.最大子矩阵和
6.背包问题
①01背包问题
②完全背包 1.最大连续子段和
这段代码是一个求最大子数组和的算法使用的是动态规划的思想。下面是代码的解释
首先定义了一个整数数组arr用于存储给定的一组数。然后定义了一个整数数组dp用于存储以arr中每个元素为结尾的最大子数组和。接着将dp的第一个元素设置为0和arr的第一个元素的最大值。然后从第二个元素开始循环遍历数组dp将当前元素的dp设置为 前一个元素的dp 和 当前元素的arr之和 与 当前元素的arr 比较最大值。最后按升序对数组dp进行排序最大子数组和即为dp的最后一个元素。
public class A {
public static void main(String[] args) {int arr[] {-2,11,-4,13,-5,-2}; //定义一个数组arrint dp[]new int[arr.length]; //定义一个数组dp长度与arr相同System.out.println(arr:Arrays.toString(arr)); //输出arr数组System.out.println(-----------流程-----------); //输出分割线dp[0]Math.max(0, arr[0]); //dp[0]为arr[0]和0的最大值System.out.println(dp:Arrays.toString(dp)); //输出dp数组for (int i 1; i dp.length; i) { //循环dp数组dp[i]Math.max(dp[i-1]arr[i], arr[i]); //dp[i]为dp[i-1]arr[i]和arr[i]的最大值System.out.println(dp[i-1]arr[i]:(dp[i-1]arr[i])\narr[i]:arr[i]); //输出dp[i-1]arr[i]和arr[i]System.out.println(dp:Arrays.toString(dp)); //输出dp数组}Arrays.sort(dp); //对dp数组进行排序System.out.println(-----------流程-----------); //输出分割线System.out.println(最大字段和dp[dp.length-1]); //输出dp数组中的最大值
}
arr:[-2, 11, -4, 13, -5, -2]
-----------流程-----------
dp:[0, 0, 0, 0, 0, 0]
dp[i-1]arr[i]:11
arr[i]:11
dp:[0, 11, 0, 0, 0, 0]
dp[i-1]arr[i]:7
arr[i]:-4
dp:[0, 11, 7, 0, 0, 0]
dp[i-1]arr[i]:20
arr[i]:13
dp:[0, 11, 7, 20, 0, 0]
dp[i-1]arr[i]:15
arr[i]:-5
dp:[0, 11, 7, 20, 15, 0]
dp[i-1]arr[i]:13
arr[i]:-2
dp:[0, 11, 7, 20, 15, 13]
-----------流程-----------
最大字段和20
分治法
最大字段和分治法递归Java 2.LCS 最大公共子序列
例如
S1{1528936}S2{568937}其最大公共子序列为{5893}。
为了找到两个字符串之间的最大公共子序列我们可以使用动态规划。基本思想是创建一个矩阵其中每个单元格表示到该点的最大公共子序列的长度。
我们从将矩阵的第一行和第一列初始化为0开始。然后对于每个后续单元格我们检查两个字符串中相应位置的字符是否匹配。如果匹配则将当前单元格的左上角对角线上的值加1。如果不匹配则取当前单元格上方和左侧单元格之间的最大值。
填充整个矩阵后最长公共子序列的长度可以在右下角单元格中找到。 public class A {
public static void main(String[] args) {String s1BDCABA;String s2ABCBDAB;int dp[][]new int[s1.length()1][s2.length()1];for (int i 0; i s1.length(); i) {for (int j 0; j s2.length(); j) {if(s1.charAt(i)s2.charAt(j)) dp[i1][j1]dp[i][j]1;else dp[i1][j1]Math.max(dp[i1][j], dp[i][j1]);}}for (int[] is : dp) {for (int i : is) {System.out.print(i );}System.out.println();}System.out.println(最大公共子序列:dp[s1.length()][s2.length()]);}
}0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1
0 0 1 1 1 2 2 2
0 0 1 2 2 2 2 2
0 1 1 2 2 2 3 3
0 1 2 2 3 3 3 4
0 1 2 2 3 3 4 4
最大公共子序列:43.LIS 最长上升子序列 动态规划解决方案的基本思想是使用一个数组 dp 来跟踪输入数组中每个索引处的最长上升子序列的长度。我们将dp初始化为所有 1因为任何索引处的最长上升子序列长度至少为 1元素本身。然后我们遍历输入数组并对于每个元素我们遍历所有先前的元素并检查它们是否小于当前元素。如果是我们将当前索引处的 dp更新为其当前值和前一个索引处的值加 1 的最大值。这意味着我们已经找到了以当前索引结尾的更长的上升子序列。最后我们输出 dp 中的最大值它表示输入数组中最长上升子序列的长度。
public class A {
public static void main(String[] args) {Scanner scannernew Scanner(System.in);int nscanner.nextInt(); //输入数组长度int arr[]new int[n]; //定义数组for (int i 0; i arr.length; i) {arr[i]scanner.nextInt(); //输入数组元素}int dp[]new int[arr.length]; //定义dp数组Arrays.fill(dp, 1); //初始化dp数组int j0;for (int i 1; i arr.length; i) {ji-1;while (j0) { if(arr[i]arr[j]) { //如果当前元素大于前面的元素dp[i]Math.max(dp[i], dp[j]1); //更新dp数组}j--;}}System.out.println(Arrays.toString(dp)); //输出dp数组Arrays.sort(dp); //对dp数组进行排序System.out.println(dp[dp.length-1]); //输出dp数组中的最大值
}
}
输入
7
1 5 2 3 11 7 9
输出
[1, 2, 2, 3, 4, 4, 5]
5 4.数塔
【动态规划】——数塔java版超详图解 5.最大子矩阵和
知识点前缀和动态规划【最大字段和】
【蓝桥杯-筑基篇】前缀和
了解决这个问题我们首先读入一个n x n的矩阵并计算每列的前缀和。然后对于每对起始和结束列我们计算它们之间的子矩阵和。
接下来我们使用动态规划来找到每列的最大子段和并相应地更新最大子矩阵和。最后我们输出最大子矩阵和。 //读入一个n*n的矩阵
//计算每一列的前缀和
//对于每一列的起始和结束位置计算出这两列之间的子矩阵和
//用dpi表示以第i列为结尾的最大子段和
//对于每一列计算以该列为结尾的最大子段和并更新ans
//输出最大子矩阵和public class B {public static void main(String[] args) {Scanner scannernew Scanner(System.in);int nscanner.nextInt();int[][] gnew int[n1][n1];for (int i 1; i g.length; i) {for (int j 1; j g.length; j) {g[i][j]scanner.nextInt();g[i][j]g[i][j]g[i-1][j]; // 计算每一列的前缀和}}for (int[] is : g) {//输出前缀和数组System.out.println(Arrays.toString(is));}int ansInteger.MIN_VALUE;for (int start 1; start g.length; start) {for (int end 1; end g.length; end) {int dpi0;for (int col 1; col g.length; col) {int aig[end][col]-g[start-1][col]; // 计算出这两列之间的子矩阵和dpiMath.max(dpiai, ai); // 计算以该列为结尾的最大子段和ansMath.max(ans, dpi); // 更新ans}}}System.out.println(--最大子矩阵和--:ans); // 输出最大子矩阵和}}4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
[0, 0, 0, 0, 0]
[0, 0, -2, -7, 0]
[0, 9, 0, -13, 2]
[0, 5, 1, -17, 3]
[0, 4, 9, -17, 1]
--最大子矩阵和--:156.背包问题
①01背包问题
解题思路使用动态规划算法解决01背包问题首先输入物品数量和背包容量然后输入每个物品的重量和价值接着使用二重循环遍历物品和背包容量如果当前背包容量大于等于当前物品重量则可以选择将该物品放入背包此时背包的价值为dp[i-1][j-wt[i]]val[i]否则背包的价值为dp[i-1][j]最后输出动态规划数组即可
/*** 01背包问题* wt: 物品重量* val: 物品价值* dp: 动态规划数组*/
public class C {public static void main(String[] args) {Scanner scannernew Scanner(System.in);int nscanner.nextInt(); // 物品数量int m scanner.nextInt(); // 背包容量int wt[]new int[n1]; // 物品重量数组int val[]new int[n1]; // 物品价值数组int dp[][]new int[n1][m1]; // 动态规划数组for (int i 1; i wt.length; i) {wt[i]scanner.nextInt(); // 输入物品重量val[i]scanner.nextInt(); // 输入物品价值}for (int i 1; i wt.length; i) {for (int j 1; j m; j) {if(j-wt[i]0) {dp[i][j]Math.max(dp[i-1][j],dp[i-1][j-wt[i]]val[i]); // 动态规划}else dp[i][j]dp[i-1][j]; // 动态规划}}for (int[] is : dp) {System.out.println(Arrays.toString(is)); // 输出动态规划数组}}}②完全背包
// 本题为完全背包问题采用动态规划求解。时间复杂度为O(nW)空间复杂度为O(nW)。
public class C {public static void main(String[] args) {int[] weights {2, 3, 4, 5}; // 物品重量int[] values {3, 4, 5, 6}; // 物品价值int capacity 8; // 背包容量int result completeKnapsack(capacity,weights, values); // 调用函数System.out.println(Maximum value: result); // 输出结果}public static int completeKnapsack(int W, int[] w, int[] v) {int n w.length; // 物品数量int[][] dp new int[n1][W1]; // 初始化动态规划数组for (int i 0; i n; i) {dp[i][0] 0; // 初始化}for (int j 0; j W; j) {dp[0][j] 0; // 初始化}for (int i 1; i n; i) {for (int j 1; j W; j) {for(int k0;k(j/w[i-1]);k) {dp[i][j] Math.max(dp[i][j], dp[i-1][j-k*w[i-1]]k*v[i-1]); // 状态转移方程}}}return dp[n][W]; // 返回最大价值}}
