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);}
}