【蓝桥杯-筑基篇】动态规划

这篇具有很好参考价值的文章主要介绍了【蓝桥杯-筑基篇】动态规划。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

🍓系列专栏:蓝桥杯

🍉个人主页:个人主页

目录

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}; //定义一个数组arr
    int 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={1,5,2,8,9,3,6},S2={5,6,8,9,3,7},其最大公共子序列为{5,8,9,3}。

为了找到两个字符串之间的最大公共子序列,我们可以使用动态规划。基本思想是创建一个矩阵,其中每个单元格表示到该点的最大公共子序列的长度。

我们从将矩阵的第一行和第一列初始化为0开始。然后,对于每个后续单元格,我们检查两个字符串中相应位置的字符是否匹配。如果匹配,则将当前单元格的左上角对角线上的值加1。如果不匹配,则取当前单元格上方和左侧单元格之间的最大值。

填充整个矩阵后,最长公共子序列的长度可以在右下角单元格中找到。

【蓝桥杯-筑基篇】动态规划

public class A {
public static void main(String[] args) {
	String s1="BDCABA";
	String s2="ABCBDAB";
	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[i+1][j+1]=dp[i][j]+1;
			else dp[i+1][j+1]=Math.max(dp[i+1][j], dp[i][j+1]);
		}
		
	}

	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 
最大公共子序列:4

3.LIS 最长上升子序列

【蓝桥杯-筑基篇】动态规划

动态规划解决方案的基本思想是使用一个数组 dp 来跟踪输入数组中每个索引处的最长上升子序列的长度我们将dp初始化为所有 1,因为任何索引处的最长上升子序列长度至少为 1(元素本身)。然后,我们遍历输入数组,并对于每个元素,我们遍历所有先前的元素并检查它们是否小于当前元素。如果是,我们将当前索引处的 dp更新为其当前值和前一个索引处的值加 1 的最大值。这意味着我们已经找到了以当前索引结尾的更长的上升子序列。最后,我们输出 dp 中的最大值,它表示输入数组中最长上升子序列的长度。

public class A {
public static void main(String[] args) {
	Scanner scanner=new Scanner(System.in);
	
	int n=scanner.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 j=0;
	for (int i = 1; i < arr.length; i++) {
		j=i-1;
	
		
	while (j>=0) {	
		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 scanner=new Scanner(System.in);
		int n=scanner.nextInt();
		int[][] g=new int[n+1][n+1];
		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 ans=Integer.MIN_VALUE;
		
			for (int start = 1; start < g.length; start++) {
				
				for (int end = 1; end < g.length; end++) {
					int dpi=0;
					for (int col = 1; col < g.length; col++) {
						
						int ai=g[end][col]-g[start-1][col]; // 计算出这两列之间的子矩阵和
						dpi=Math.max(dpi+ai, ai); // 计算以该列为结尾的最大子段和
						ans=Math.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]
--最大子矩阵和--:15

6.背包问题

①01背包问题

解题思路:使用动态规划算法解决01背包问题,首先输入物品数量和背包容量,然后输入每个物品的重量和价值,接着使用二重循环遍历物品和背包容量,如果当前背包容量大于等于当前物品重量,则可以选择将该物品放入背包,此时背包的价值为dp[i-1][j-wt[i]]+val[i],否则背包的价值为dp[i-1][j],最后输出动态规划数组即可文章来源地址https://www.toymoban.com/news/detail-423531.html

/**
 * 01背包问题
 * wt: 物品重量
 * val: 物品价值
 * dp: 动态规划数组
 */
public class C {
	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		int n=scanner.nextInt(); // 物品数量
		int m =scanner.nextInt(); // 背包容量
		int wt[]=new int[n+1]; // 物品重量数组
		int val[]=new int[n+1]; // 物品价值数组
		int dp[][]=new int[n+1][m+1]; // 动态规划数组
		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[n+1][W+1]; // 初始化动态规划数组
	    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 k=0;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]; // 返回最大价值
	}


}

到了这里,关于【蓝桥杯-筑基篇】动态规划的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • MySQL筑基篇之增删改查

    ✅作者简介:C/C++领域新星创作者,为C++和java奋斗中 ✨个人社区:微凉秋意社区 🔥系列专栏:MySql一点通 📃推荐一款模拟面试、刷题神器👉注册免费刷题 🔥前言 本文将承接前两篇MySQL专栏的博文,讲解数据库的 增删改查 操作,这里的查询确切的说应该是初级的查询,不

    2024年02月12日
    浏览(57)
  • 百日筑基篇——python爬虫学习(一)

    百日筑基篇——python爬虫学习(一) 随着学习的深入,有关从各种不同的数据库中以及互联网上的海量信息,如何有选择性的爬取我们所需的数据以方便我们的数据分析工作,爬虫的学习是必要的。 Python爬虫是指使用Python编程语言编写的程序,通过模拟浏览器行为从网页中

    2024年02月13日
    浏览(52)
  • 算法修炼之筑基篇——筑基一层中期(解决01背包,完全背包,多重背包)

    ✨ 博主: 命运之光​​​​​​ 🦄 专栏: 算法修炼之练气篇​​​​​ 🍓 专栏: 算法修炼之筑基篇 ✨ 博主的其他文章: 点击进入博主的主页​​​​​​ 前言: 学习了算法修炼之练气篇想必各位蒟蒻们的基础已经非常的扎实了,下来我们进阶到算法修炼之筑基篇的

    2024年02月08日
    浏览(34)
  • 蓝桥杯丨动态规划

    做你想做的,错的算我的 这里是Want595,欢迎光临我的世界 ~   目录 前言  一、斐波那契式 通项公式:f(n)=f(n-1)+f(n-2)  举例说明 爬楼梯  骨牌铺方格  一只小蜜蜂 二、背包问题 通项公式:f(i,j)=max(f(i-1,j),f(i-1(或i),j-w(i))+v(i))  举例说明  0-1背包问题  完全背包问题  矿工

    2024年02月11日
    浏览(36)
  • 蓝桥杯动态规划基础篇(一)

    动态规划(Dynamic Programming,DP)是运筹学的一个分支,是求解决策过程最优化的过程。20世纪50年代初,美国数学家贝尔曼(R.Bellman)等人在研究多阶段决策过程的优化问题时,提出了著名的最优化原理,从而创立了动态规划。动态规划的应用极其广泛,包括工程技术、经济、

    2024年02月03日
    浏览(38)
  • 蓝桥杯(路径 动态规划 C++)

     思路: 1、利用动态规划的思想。 2、用f[i]来记录从第一个点到第i个点的最短距离。 3、f[i]赋值分两种情况,第一种:f[i]为0的时候,也就是第一种刚到i点的情况,记录其距离为最小公倍数;第二种:f[i]已经有值了,比较新的点到其距离和之前点到其距离,取小的赋值。

    2024年02月07日
    浏览(38)
  • 【蓝桥杯/动态规划】数的计算

    题目描述 输入一个自然数 n (n≤1000)n (n leq 1000) n   ( n ≤ 1 0 0 0 ) ,我们对此自然数按照如下方法进行处理: 不作任何处理; 在它的左边加上一个自然数,但该自然数不能超过原数的一半; 加上数后,继续按此规则进行处理,直到不能再加自然数为止。 问总共可以产生多少个数。

    2024年02月01日
    浏览(49)
  • 蓝桥杯-动态规划-子数组问题

    目录 一、乘积最大数组 二、乘积为正数的最长子数组长度 三、等差数列划分 四、最长湍流子数组 心得: 最重要的还是状态表示,我们需要根据题的意思,来分析出不同的题,不同的情况,来分析需要多少个状态 乘积最大数组 1.状态表示 dp[i]:到达i位置的最大乘积子数组。

    2024年02月05日
    浏览(36)
  • 蓝桥杯-回路计数(状态压缩、动态规划)

    蓝桥学院由 21 21 21 栋教学楼组成,教学楼编号 11 11 11 ​​ 到 21 21 21 ​​。对于两栋教学楼 a a a 和 b b b ​,当 a a a 和 b b b 互质时, a a a 和 b b b 之间有一条走廊直接相连,两个方向皆可通行,否则没有直接连接的走廊。 小蓝现在在第一栋教学楼,他想要访问每栋教学楼正

    2024年02月08日
    浏览(60)
  • 蓝桥:保险箱(Python,动态规划)

    小蓝有一个保险箱,保险箱上共有 n 位数字。小蓝可以任意调整保险箱上的每个数字,每一次操作可以将其中一位增加 1 或减少 1。当某位原本为 9 或 0 时可能会向前(左边)进位/退位,当最高位(左边第一位)上的数字变化时向前的进位或退位忽略。 例如: 00000 的第 5 位减

    2024年04月09日
    浏览(92)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包