1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
package 动态规划;

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

/**
 * @author: DreamCode
 * @file: 硬币支付问题.java
 * @time: 2022-4-2-20:52:23
 * @method: 分别采用基本DFS以及DFS+备忘录进行搜索。这里尝试使用动态规划无果，可能的原因是在自底向上逐步迭代的时候，有些硬币的             数值是无法凑出来的
 */
public class 硬币支付问题 {

	static int[] cnts = new int[6];
	static int[] coins = { 1, 5, 10, 50, 100, 500 };
	static int[][] rec; // 备忘录递归

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		for (int i = 0; i < 6; i++) {
			cnts[i] = scanner.nextInt();
		}
		int A = scanner.nextInt();
		int ans = DFS(A, 5); // DFS递归
		rec = new int[A + 1][6];
		int ans2 = rec_DFS(A, 5); // 备忘录式递归
		System.out.println(ans);
		System.out.println(ans2);
	}

	private static int rec_DFS(int a, int k) {
		// TODO 备忘录递归
		if (a == 0) {
			return 0;
		}
		if (k == 0) {
			return a;
		}
		if (rec[a][k] != 0) {
			return rec[a][k];
		}
		int count = a / coins[k];
		count = Math.min(count, cnts[k]);
		int res = count + rec_DFS(a - count * coins[k], k - 1);
		rec[a][k] = res;
		return res;
	}

	private static int DFS(int a, int k) {
		// TODO 深搜递归
		if (k == 0) {
			return a;
		}
		if (a == 0) {
			return 0;
		}
		int count = a / coins[k];
		count = Math.min(count, cnts[k]);
		return count + DFS(a - count * coins[k], k - 1);
	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
package 动态规划;

/**
 * @author: DreamCode
 * @file: 钢条切割问题.java
 * @time: 2022-4-3-10:18:55
 * @method: 递归方法：当前的钢条长度i支持前j种切割方法，别人遍历每一种切割方法，记录最优解；
 *          动态规划方法：钢条长度为0的时候最优解肯定为0，钢条长度从1到n逐步迭代，对于每次的钢条长度i，找出支持的j种切割方法             种的最优解
 */
public class 钢条切割问题 {

	static int[] p = { 1, 5, 8, 16, 10, 17, 17, 20, 24, 30 };
	static int n = 10;
	static int[] rec;

	public static void main(String[] args) {
		int ans_dfs = DFS(n);  //深搜DFS
		System.out.println(ans_dfs);
		rec = new int[n + 1];
		int ans_rec = rec_DFS(n); // 备忘录方法
		System.out.println(ans_rec);
		int ans_dp = DP(); // 动态规划算法求解最优解
		System.out.println(ans_dp);
	}

	private static int DP() {
		// TODO 动态规划算法求解最优解
		int[] dp = new int[n + 1];
		dp[0] = 0; // 钢条长度为0时的价值为0
		for (int i = 1; i <= n; i++) { // 这里的j是p的下标，从0~n-1；但是实际切割长度是1~n；所以这里是j+1代表切割长度
			for (int j = 0; i >= (j + 1) && j < p.length; j++) { // 当前的钢条长度i支持切割大小为j的长度
				dp[i] = Math.max(dp[i], dp[i - (j + 1)] + p[j]); // 不切与切，选择最优子问题
			}
		}

		return dp[n];
	}

	private static int rec_DFS(int k) {
		// TODO DFS+备忘录获得最优解
		if (k == 0) { // 当前钢条长度为0
			return 0;
		}
		if (rec[k] != 0) {
			return rec[k];
		}
		int res = 0;
		for (int i = 1; i <= p.length; i++) { // 切的长度是1到n，等于n代表整体，不用切
			if (k >= i) { // 当前的长度支持切
				res = Math.max(res, p[i - 1] + rec_DFS(k - i));
			}
		}
		rec[k] = res;
		return res;
	}

	private static int DFS(int k) {
		// TODO DFS深搜遍历获得最优解
		if (k == 0) { // 当前钢条长度为0
			return 0;
		}
		int res = 0;
		for (int i = 1; i <= p.length; i++) { // 切的长度是1到n，等于n代表整体，不用切
			if (k >= i) { // 当前的长度支持切
				res = Math.max(res, p[i - 1] + DFS(k - i));
			}
		}
		return res;
	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
package 动态规划;

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

/**
 * @author: DreamCode
 * @file: 数字三角形.java
 * @time: 2022-4-3-14:37:49
 * @method: DFS：从顶点逐步往下递归，每次将当前顶点的值加上两条分支中的最大值，当到达最底层时，直接将节点的值返回。 动态规划：
 */
public class 数字三角形 {

	/**
	 * 在数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。<br>
	 * 路径上的每一步都只能往左下或 右下走。只需要求出这个最大和即可，不必给出具体路径。<br>
	 * 三角形的行数大于1小于等于100，数字为 0 - 99 输入格式 5 //表示三角形的行数 接下来输入三角形 7 3 8 8 1 0 2 7 4 4 4
	 * 5 2 6 5 要求输出最大和
	 *
	 */
	static int n;
	static int[][] rec;

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt();
		int[][] arr = new int[n][n];
		rec = new int[n + 1][n + 1];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= i; j++) {
				arr[i][j] = scanner.nextInt();
			}
		}
		int ans_dfs = DFS(Arrays.copyOf(arr, n), 0, 0); // DFS方法求最优解
		int ans_dp = DP(Arrays.copyOf(arr, n)); // 动态规划求解
		System.out.println(ans_dfs);
		System.out.println(ans_dp);

	}

	private static int DP(int[][] arr) {
		// TODO 动态规划法求解
		int[] dp=new int[arr.length];
		dp = arr[arr.length-1];  //初始化dp数组记录为倒数第一行的值
		for(int i=arr.length-2;i>=0;i--) {  //结合滚动数组，从倒数第二行逐步往上递推
			for(int j=0;j<=i;j++) {
				dp[j]=arr[i][j]+Math.max(dp[j], dp[j+1]);
			}
		}
		return dp[0];
	}

	private static int DFS(int[][] arr, int x, int y) {
		// TODO DFS方法求最优解
		if (x == arr.length - 1) {
			return arr[x][y];
		}
		if (rec[x][y] != 0)
			return rec[x][y];
		int res = arr[x][y];
		res += Math.max(DFS(arr, x + 1, y), DFS(arr, x + 1, y + 1));
		rec[x][y] = res;
		return res;
	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
package 动态规划;

import java.util.Scanner;

/**
 * @author: DreamCode
 * @file: 完全背包问题.java
 * @time: 2022-4-3-15:46:27
 * @method: DFS：在当前背包容量为i的情况下，当前的物品可选，选择能让价值最大 的数目或者是不选；当前物品不支持选，直接进入下一	           层;
            动态规划：初始化状态包括只有第一个物品与背包容量为0的情况，逐步递推前i种物品下，背包容量为j的最优子问题。这里在选             与不选第i个物品中取最大值时,因为每个物品有无数个，所以如果当前选择了第i种物品，那么接下来依然有i种物品可选
 */
public class 完全背包问题 {
	static int[] values = { 9, 5, 3, 1 };
	static int[] weights = { 7, 4, 3, 2 };
	static int n = 4;
	static int total = 100;
	static int[][] rec;

	public static void main(String[] args) {
		rec = new int[total + 1][n + 1];
		int ans_dfs = DFS(total, 0);
		System.out.println(ans_dfs);
		int ans_dp = DP();
		System.out.println(ans_dp);
	}

	private static int DP() {
		// TODO 动态规划求最优解
		int[][] dp = new int[n][total + 1];
		for (int i = 0; i <= total; i++) { // 初始化第一行，只有一种物品，尽可能多拿就行
			if (i >= weights[0]) {
				dp[0][i] = (i / weights[0]) * values[0];
			} else {
				dp[0][i] = 0;
			}
		}
		for (int i = 0; i < n; i++) {// 初始化第一列，当所剩空间为0时，没法选任何物品
			dp[i][0] = 0;
		}
		for (int i = 1; i < n; i++) {
			for (int j = 1; j <= total; j++) {
				if (j >= weights[i]) { // 当前j空间大小支持选择第i中物品
					dp[i][j] = Math.max(dp[i][j - weights[i]]+values[i], dp[i - 1][j]); // 选与不选中取最大值,这里因为有无数个物品，所以如果当前选择了第i种物品，那么接下来还是依然有i种物品可选
				} else {
					dp[i][j] = dp[i - 1][j];
				}
			}
		}
		return dp[n-1][total];
	}

	private static int DFS(int N, int k) {
		// TODO DFS求最优解，N为当前背包剩余的容量，k为当前可选的物品
		if (rec[N][k] != 0)
			return rec[N][k];
		if (k == n) {
			return 0;
		}
		int res = 0;
		for (int i = 0; i <= N / weights[k]; i++) {
			res = Math.max(i * values[k] + DFS(N - i * weights[k], k + 1), res);
		}
		rec[N][k] = res;
		return res;
	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
package 动态规划;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author: DreamCode
 * @file: 最大公共子序列.java
 * @time: 2022-4-3-15:02:07
 * @method:DFS:利用list存储两字符串相同的字符，逐个比较s1与s2的字符，如果当前字符相同，则递归查询字串的最长公共子序列，将公            共子序列的公共字符加入到当前字符list中，总是维护更新一个最长的公共字符list；
 		  动态规划法：当s1[i]==s2[j]时:dp[i][j] = dp[i - 1][j - 1] + 1;
 		             否则dp[i][j] = Math.max(dp[i - 1][j], dp[i][j- 1]);
 */
public class 最大公共子序列 {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String s1 = scanner.next();
		String s2 = scanner.next();
		String dfs_ans = DFS(s1, s2).toString();
		System.out.println(dfs_ans);
		String ans_dp = DP(s1, s2); // 动态规划求解
		System.out.println(ans_dp);
	}

	private static String DP(String s1, String s2) {
		// TODO 动态规划求解子问题
		int len1 = s1.length();
		int len2 = s2.length();
		int[][] dp = new int[len1][len2];
		for (int i = 0; i < len1; i++) { // 初始化第一列
			if (i > 0 && dp[i - 1][0] == 1) {
				dp[i][0] = 1;
			} else {
				if (s1.charAt(i) == s2.charAt(0)) {
					dp[i][0] = 1;
				} else {
					dp[i][0] = 0;
				}
			}
		}
		for (int i = 0; i < len2; i++) {// 初始化第一行
			if (i > 0 && dp[0][i - 1] == 1) {
				dp[0][i] = 1;
			} else {
				if (s1.charAt(0) == s2.charAt(i)) {
					dp[0][i] = 1;
				} else {
					dp[0][i] = 0;
				}
			}
		}
		for (int i = 1; i < len1; i++) {
			for (int j = 1; j < len2; j++) {
				if (s1.charAt(i) == s2.charAt(j)) {
					dp[i][j] = dp[i - 1][j - 1] + 1;
				} else {
					dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
				}
			}
		}
		return parseString(dp, s1, s2);
	}

	private static String parseString(int[][] dp, String s1, String s2) {
		// TODO 解析出最长公共子序列
		StringBuilder res = new StringBuilder();
		int len1 = s1.length() - 1;
		int len2 = s2.length() - 1;
		while (len1 > 0 && len2 > 0) {
			if (dp[len1][len2] > dp[len1 - 1][len2] && dp[len1][len2] > dp[len1][len2 - 1]) {// 比左和上大，一定是当前位置的字符相等
				res.insert(0, s1.charAt(len1));
				len1--;
				len2--;
			} else if (dp[len1 - 1][len2] >= dp[len1][len2 - 1]) {
				len1--;
			} else {
				len2--;
			}

		}
		if (len1 == 0 && len2 == 0 &&dp[0][0]==1) {
			res.insert(0, s2.charAt(0));
		} else if (len2 == 0 && dp[len1][0] == 1) {
			res.insert(0, s2.charAt(0));
		} else if (len1 == 0 && dp[0][len2] == 1) {
			res.insert(0, s1.charAt(0));
		}
		return res.toString();
	}

	private static List<Character> DFS(String s1, String s2) {
		// TODO DFS查询最长公共子序列
		List<Character> ans = new ArrayList<>();
		for (int i = 0; i < s1.length(); i++) {
			List<Character> list = new ArrayList<>();
			for (int j = 0; j < s2.length(); j++) {
				if (s1.charAt(i) == s2.charAt(j)) { // s1的第i个字符与s2的第j个字符相同，进行递归
					list.add(s1.charAt(i));
					list.addAll(DFS(s1.substring(i + 1), s2.substring(j + 1)));
					break;
				}
			}
			if (list.size() > ans.size()) {
				ans = list;
			}
		}
		return ans;
	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
package 动态规划;

import java.util.Scanner;

/**
 * @author: DreamCode
 * @file: 最长递增子序列的长度.java
 * @time: 2022-4-3-19:58:35
 * @method: 尺取法遍历，时间复杂度为n^2
 		   动态规划法1：对于第i个字符，在前i-1个最短递增子序列种，当arr[i]>arr[j]时：dp[i]=Math.max(dp[i], dp[j]+1);
 		   否则，arr[i]为前i个数中最小的值，dp[i]=1；
 		   动态规划法2：dp[p]记录的是当前长度p的最长递增子序列的最后一个元素。
 		   对于每一个arr[i],如果arr[i]>dp[p],则dp[p+1]=arr[i];
 		   否则，扫描dp数组，替换第一个比arr[i]大的dp[j]。因为对于递增子序列来说，末尾的数越小，则其能继续递增的机会越大
 */
public class 最长递增子序列的长度 {

	static int[] arr = {4, 2, 3, 1, 5, 6, 4, 8, 5, 9};
	public static void main(String[] args) {
		int ans = f();
		System.out.println(ans);
		int ans_dp=DP();
		System.out.println(ans_dp);
		int ans_dp2=DP2();
		System.out.println(ans_dp2);

	}
	private static int DP2() {
		// TODO 第二种动态规划方法
		int[] dp = new int[arr.length + 1];
	    dp[1] = arr[0];//长度为1的最长递增子序列，初始化为第一个元素
	    int p = 1;//记录dp更新的最后位置
	    for (int i = 1; i < arr.length; i++) {
	      if (arr[i] > dp[p]) {
	        dp[p + 1] = arr[i];
	        p++;
	      } else {
	        //扫描dp数组，替换第一个比arr[i]大的dp
	         for (int j = 0; j <= p; j++) {
	           if (dp[j]>arr[i]){
	             dp[j]=arr[i];
	             break;
	           }
	         }
	      }
	    }   
		return p;
	}
	private static int DP() {
		// TODO 第一种动态规划法求最优解
		int len=arr.length;
		int[] dp=new int[len];
		dp[0]=1;  //第一个数单独组成一个递增序列
		for(int i=1;i<len;i++) {
			for(int j=i-1;j>=0;j--) {
				if(arr[i]>arr[j]) {
					dp[i]=Math.max(dp[i], dp[j]+1);
				}
			}
			if(dp[i]==0) {
				dp[i]=1;
			}
		}
		return dp[len-1];
	}
	private static int f() {
		// TODO 尺取法获取最优解
		int len=arr.length;
		int maxCnt=0;
		for(int i=0;i<len;i++) {
			int cnt=1;
			int p=i;
			for(int j=i+1;j<len;j++) {
				if(arr[j]>arr[p]) {
					p=j;
					cnt++;
				}
			}
			maxCnt=Math.max(cnt, maxCnt);
		}
		return maxCnt;
	}

}