一、字符串变形
输入两个字符串a和b，a的长度小于b的长度。现在可以在a中的每个位置插入任意字符，使得最终a的长度等于b的长度，问最后a和b中对应位置字符不同的位置的个数。
这个问题可以看做是：带约束的最长公共子序列
考虑形如abcx 和ayybc的两个字符串，第一个字符串不能添加太多字符，否则会导致它的长度太长。当a[i]=b[j]时，i必须不能大于j，否则a[i]是不可能等于j的。这道题测试样例过于简单，以至于很多错误解法也能全部通过。
import java.util.Scanner; public class Main {Main() { Scanner cin = new Scanner(System.in); char[] a = cin.next().trim().toCharArray(), b = cin.next().trim().toCharArray(); int[][] m = new int[a.length][b.length]; for (int i = 0; i < a.length; i++) { for (int j = 0; j < b.length; j++) { if (i > 0) m[i][j] = Math.max(m[i - 1][j], m[i][j]); if (j > 0) m[i][j] = Math.max(m[i][j - 1], m[i][j]); if (a[i] == b[j] && a.length - i <= b.length - j && i <= j) { int last = 0; if (i > 0 && j > 0) last = m[i - 1][j - 1]; m[i][j] = Math.max(m[i][j], last + 1); } } } int common = m[a.length - 1][b.length - 1]; int add = b.length - a.length;// System.out.println(common); int ans = b.length - common - add; System.out.println(ans);} public static void main(String[] args) { new Main();}} 二、概率+动态规划
N个人，M个礼品，每个礼品的个数为C[i]，第i个人选择第j个礼品的概率为p[i][j]，当发放礼品时，N个人一次性确定好自己要什么礼品，然后按照顺序一次发放，若某种类型的礼品没了，就不给要这个礼品的人发了。因为礼品个数有限，问期望有多少人能够拿到礼品。
关键在于明白问题转化：期望拿到礼品的人数=每种礼品期望发给的任务。因为人和礼品之间时一一对应的。
定义数组f[M][N],f[i][j]表示第i种礼品被要求次数为j的概率，N从0~N递增推导就可以得到最终矩阵，这个过程相当于滚动数组形式的动态规划。import java.util.Scanner; public class Main {int N, M;int[] c;double p[][];double left[][]; Main() { Scanner cin = new Scanner(System.in); N = cin.nextInt(); M = cin.nextInt(); c = new int[M]; p = new double[N][M]; for (int i = 0; i < M; i++) { c[i] = cin.nextInt(); if (c[i] > N) c[i] = N; } for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) p[i][j] = cin.nextDouble(); left = new double[M][N + 1]; for (int i = 0; i < left.length; i++) left[i][0] = 1; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { for (int k = N; k >= 0; k--) { left[j][k] = left[j][k] * (1 - p[i][j]); if (k > 0) { left[j][k] += left[j][k - 1] * p[i][j]; } } } } double s = 0; for (int i = 0; i < M; i++) { for (int j = 0; j <= N; j++) { s += left[i][j] * Math.min(c[i], j); } } System.out.printf("%.1f", s);} public static void main(String[] args) { new Main();}} 三、数组排序：贪心
一个无序数组，每次只能执行一种操作：把任意一个元素移动到末尾。问最少经过多少次操作能够使得数组变得有序。
对于元素x，只要它后面有比它小的元素，它就必然要被挪到最后去。而对于需要挪到最后去的一批元素，必然是优先移动比较小的那些元素，这样才能保证它们尽量靠前。
import java.io.IOException;import java.util.Arrays;import java.util.Comparator;import java.util.LinkedList;import java.util.Scanner;import java.util.stream.Collectors; public class Main {Main() { Scanner cin = new Scanner(System.in); int N = cin.nextInt(); int[] a = new int[N]; for (int i = 0; i < N; i++) a[i] = cin.nextInt(); int s = 0; while (true) { LinkedList left = new LinkedList<>(); LinkedList right = new LinkedList<>(); int mi = Integer.MAX_VALUE; for (int i = a.length - 1; i >= 0; i--) { if (mi < a[i]) { right.add(a[i]); } else { left.add(a[i]); } mi = Math.min(mi, a[i]); } right.sort(Comparator.comparing(x -> x)); s += right.size(); if (right.size() == 0) break; int ai = 0; for (int i : left) a[N - 1 - right.size() - (ai++)] = i; for (int i : right) a[ai++] = i; } System.out.println(s);} public static void main(String[] args) { new Main();}}