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

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< 判断是否被标记： (i & (1< 判断是否包含：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);
 
    }
}