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

素颜马尾好姑娘i 2024-04-20 07:50 82阅读 0赞

> ?系列专栏:[蓝桥杯][Link 1]
> 
> ?个人主页:[个人主页][Link 2]

**目录**

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）][Java]

### 2.LCS 最大公共子序列 ###

例如：

S1=\{1，5，2，8，9，3，6\}，S2=\{5，6，8，9，3，7\}，其最大公共子序列为\{5，8，9，3\}。

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

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

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

![e2ac200472414456aafe2ceec941347d.png][]

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 最长上升子序列 ###

![577bf241f0754391be526be5f737b85c.png][]

动态规划解决方案的基本思想是**使用一个数组 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版，超详图解）][java]

### 5.最大子矩阵和 ###

**知识点：前缀和+动态规划【最大字段和】**

[【蓝桥杯-筑基篇】前缀和][-]

了解决这个问题，我们首先读入一个n x n的矩阵，并计算每列的前缀和。然后，对于每对起始和结束列，我们计算它们之间的子矩阵和。

接下来，我们使用动态规划来找到每列的最大子段和，并相应地更新最大子矩阵和。最后，我们输出最大子矩阵和。

![475a06c01a8a4c028681bb358f0b952d.png][]

![6ba12bdfe30c4f3c8908db40d6f28688.png][]

//读入一个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\]**，最后输出动态规划数组即可

/**
     * 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]; // 返回最大价值
    	}
    
    
    }

[Link 1]: https://blog.csdn.net/javascript_tsj/category_12167433.html
[Link 2]: https://blog.csdn.net/Javascript_tsj?type=blog
[Java]: https://blog.csdn.net/Javascript_tsj/article/details/123882411
[e2ac200472414456aafe2ceec941347d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/b6586a0a88ed42749fcd9ab2295f2913.png
[577bf241f0754391be526be5f737b85c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/dea0d30cda37428bbbe5cd576a72b4bd.png
[java]: https://blog.csdn.net/Javascript_tsj/article/details/124402913
[-]: https://blog.csdn.net/Javascript_tsj/article/details/129469090?spm=1001.2014.3001.5501
[475a06c01a8a4c028681bb358f0b952d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/0410f7dcbfa74e88ad46e788c3558300.png
[6ba12bdfe30c4f3c8908db40d6f28688.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/d7de58626f134f82a73058415bc1108f.png