蓝桥杯备赛第五篇（动态规划）

本文主要是介绍蓝桥杯备赛第五篇（动态规划），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.数位dp

public class Main {static long[] limit;static int length;static long[][] dp;public static long dfs(int pos, int pre, boolean flag, boolean lead) {if (pos == length) return 1;if (!flag && !lead && dp[pos][pre] != -1) return dp[pos][pre];long max = (flag ? limit[pos] : 进制数);long sum = 0;for (int i = 0; i <= max; i++) {if (条件) {sum += dfs(pos + 1, i, flag && i == limit[pos], lead && i == 0);}}if (!flag && !lead) dp[pos][pre] = sum;return sum;}public static long solve(long num) {if (num == 0) return 1;length = ("" + num).length();limit = new long[length];dp = new long[length][10];for (int i = 0; i < length; i++) {Arrays.fill(dp[i], -1);}for (int i = length - 1; i >= 0; i--) {limit[i] = num % 进制数;num /= 进制数;}return dfs(0, 0, true, true);}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int a = scanner.nextInt();int b = scanner.nextInt();System.out.println(solve(b) - solve(a - 1));}
}

2.状态压缩dp

这一部分没有统一的算法模板，只有对二进制操作熟悉之后才能做好这类题，所以我在此总结几个操作。

进行标记：i | (1<<j)
判断是否被标记： (i & (1<<j))==0
判断是否包含：a | b == b
当前行选的元素不能相邻：now & (now >> 1) == 0
当前行与上一行的选择上下也不能相邻：pre & now == 0
注意：添加状态用 | ，删除状态用 ^,判断状态用 &

3.最长公共子序列

public class Main {public static void main(String[] args) {char[] str1 = "abcdefgh".toCharArray();char[] str2 = "acjlfabhh".toCharArray();int[][] dp = new int[str1.length + 1][str2.length + 1];for (int i = 1; i <= str1.length; i++) {for (int j = 1; j <= str2.length; j++) {if (str1[i - 1] == str2[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[str1.length][str2.length]);}
}

4.最大连续子序列和

public class Main {public static void main(String[] args) {int[] arr = new int[]{-2, 11, -4, 13, -5, -2};int[] dp = new int[arr.length];dp[0] = arr[0];int max = arr[0];for (int i = 1; i < arr.length; i++) {dp[i] = Math.max(dp[i - 1] + arr[i], arr[i]);max = Math.max(max, dp[i]);}System.out.println(max);}
}

5.最长上升子序列

public class Main {public static void main(String[] args) {int[] arr = new int[]{2, 1, 5, 3, 6, 4, 6, 3};int[] dp = new int[arr.length];dp[0] = 1;int max = dp[0];for (int i = 1; i < arr.length; i++) {for (int j = i - 1; j >= 0; j--) {if (arr[i] > arr[j]) {dp[i] = Math.max(dp[i], dp[j] + 1);}max = Math.max(max, dp[i]);}}System.out.println(max);}
}