【蓝桥杯省赛】冲刺练习题【动态规划】倒计时【08】天

3

4

5

13

import java.util.Scanner;
public class dp_1 {
//三步问题
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] dp=new int[n+3];
        dp[1]=1;
        dp[2]=2;
        dp[3]=4;
        for (int i = 4; i <= n; i++) {
            dp[i]=(dp[i-1]+dp[i-2]+dp[i-3])%1000000007;
        }
        System.out.println(dp[n]);
    }
}

[-2,1,-3,4,-1,2,1,-5,4]

6

import java.util.Arrays;
import java.util.Scanner;

public class demo {
//连续数列
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		String str=sc.nextLine();
		str=str.substring(1,str.length()-1);
		String[] a=str.split(",");
		int[] dp=new int[a.length];
		//字符串数组转int数组
		int[] s=Arrays.stream(a).mapToInt(Integer::parseInt).toArray();
		dp[0]=s[0];
		int max=s[0];
		for (int i = 1; i < a.length; i++) {
			dp[i]=Math.max(dp[i-1]+s[i], s[i]);
			max=Math.max(max, dp[i]);
		}
		System.out.println(max);
	}
}

[1,2,3,1]

4

[2,7,9,3,1]

12

import java.util.Arrays;
import java.util.Scanner;
public class demo {
//打家劫舍
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		String str=sc.nextLine();
		if(str.length()==0) {
			System.out.println(0);
			return;
		}
		if(str.length()==1) {
			System.out.println(str);
			return;
		}
		str=str.substring(1,str.length()-1);
		String[] a=str.split(",");
		int[] s=Arrays.stream(a).mapToInt(Integer::parseInt).toArray();
		int[] dp=new int[a.length];
		dp[0]=s[0];
		dp[1]=Math.max(dp[0], s[1]);
		for (int i = 2; i < a.length; i++) {
			dp[i]=Math.max(dp[i-1], dp[i-2]+s[i]);
		}
		System.out.println(dp[s.length-1]);

	}

}

3 2

3

7 3

28

import java.util.Scanner;
public class demo {
//不同路径
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int m=sc.nextInt();
        int n=sc.nextInt();
        int[][] dp=new int[m][n];
        for (int i = 0; i < n; i++)dp[0][i]=1;
        for (int i = 0; i < m; i++)dp[i][0]=1;
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[i].length; j++) {
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        System.out.println(dp[m-1][n-1]);

    }

}

3 3
1 3 1
1 5 1
4 2 1

7

import java.util.Scanner;
public class dp_5 {
//最小路径和
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int m=sc.nextInt();
		int n=sc.nextInt();
		int[][] a=new int[m][n];
		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a[i].length; j++) {
				a[i][j]=sc.nextInt();
			}
		}
		int[][] dp=new int[m][n];
		dp[0][0]=a[0][0];
		for (int i = 1; i < m; i++)dp[0][i]=dp[0][i-1]+a[0][i];
		for (int i = 1; i < n; i++)dp[i][0]=dp[i-1][0]+a[i][0];
		for (int i = 1; i < dp.length; i++) {
			for (int j = 1; j < dp.length; j++) {
				dp[i][j]=Math.min(dp[i-1][j], dp[i][j-1])+a[i][j];
			}
		}
		System.out.println(dp[m-1][n-1]);

	}

}

abcde
ace

3

abc
abc

3

import java.util.Scanner;
public class dp_6 {
//最长公共子序列
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		String text1=sc.nextLine();
		String text2=sc.nextLine();
		int[][] dp=new int[10000][10000];
		for (int i = 1; i <= text1.length(); i++) {
			for (int j = 1; j <= text2.length(); j++) {
				if(text1.charAt(i-1)==text2.charAt(j-1)) {
					dp[i][j]=dp[i-1][j-1]+1;
				}else {
					dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]);
				}
			}
		}
		System.out.println(dp[text1.length()][text2.length()]);
	}

}