admin管理员组文章数量:1530520
暴力递归与动态规划
- 暴力递归
- 习题1 打印n层汉诺塔从最左边移动到最右边的全部过程
- 习题2 给你一个栈，请你逆序这个栈，不能申请额外的数据结构，只能使用递归函数。 如何实现?
- 习题3 打印一个字符串的全部子序列，要求不要出现重复的排列
- 习题4 打印一个字符串的全部排列，要求不要出现重复的排列
- 动态优化
- 习题5 假设有排成一行的N个位置，记为1~N，N 一定大于或等于 2开始时机器人在其中的M位置上(M 一定是 1~N 中的一个)如果机器人来到1位置，那么下一步只能往右来到2位置；如果机器人来到N位置，那么下一步只能往左来到 N-1 位置；如果机器人来到中间位置，那么下一步可以往左走或者往右走；规定机器人必须走 K 步，最终能来到P位置(P也是1~N中的一个)的方法有多少种给定四个参数 N、M、K、P，返回方法数。
- 习题6 给定一个整型数组arr，代表数值不同的纸牌排成一条线玩家A和玩家B依次拿走每张纸牌规定玩家A先拿，玩家B后拿但是每个玩家每次只能拿走最左或最右的纸牌玩家A和玩家B都绝顶聪明请返回最后获胜者的分数。
- 习题7 给定两个长度都为N的数组weights和values，weights[i]和values[i]分别代表 i号物品的重量和价值。给定一个正数bag，表示一个载重bag的袋子，你装的物品不能超过这个重量。返回你能装下最多的价值是多少?
- 习题8 规定1和A对应、2和B对应、3和C对应...26和Z对应那么一个数字字符串比如"111”就可以转化为:"AAA"、"KA"和"AK"给定一个只有数字字符组成的字符串str，返回有多少种转化结果
- 习题9 给定一个字符串str，给定一个字符串类型的数组arr，出现的字符都是小写英文arr每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来返回需要至少多少张贴纸可以完成这个任务。例子：str= "babac"，arr = {"ba","c","abcd"}ba + ba + c 3 abcd + abcd 2 abcd+ba 2所以返回2
- 习题10 给定两个字符串str1和str2，返回这两个字符串的最长公共子序列长度比如 ： str1 = “a12b3c456d”,str2 = “1ef23ghi4j56k”最长公共子序列是“123456”，所以返回长度6
- 习题11 给定一个字符串str，返回这个字符串的最长回文子序列长度比如 ： str = “a12b3c43def2ghi1kpm”最长回文子序列是“1234321”或者“123c321”，返回长度7
- 习题12 请同学们自行搜索或者想象一个象棋的棋盘，然后把整个棋盘放入第一象限，棋盘的最左下角是(0,0)位置那么整个棋盘就是横坐标上9条线、纵坐标上10条线的区域给你三个 参数 x，y，k返回“马”从(0,0)位置出发，必须走k步最后落在(x,y)上的方法数有多少种?
- 习题13 给定一个数组arr，arr[i]代表第i号咖啡机泡一杯咖啡的时间给定一个正数N，表示N个人等着咖啡机泡咖啡，每台咖啡机只能轮流泡咖啡只有一台咖啡机，一次只能洗一个杯子，时间耗费a，洗完才能洗下一杯每个咖啡杯也可以自己挥发干净，时间耗费b，咖啡杯可以并行挥发假设所有人拿到咖啡之后立刻喝干净，返回从开始等到所有咖啡机变干净的最短时间三个参数：int[] arr、int N，int a、int b
- 习题14 给定一个二维数组matrix，一个人必须从左上角出发，最后到达右下角沿途只可以向下或者向右走，沿途的数字都累加就是距离累加和返回最小距离累加和
- 习题15 arr是货币数组，其中的值都是正数。再给定一个正数aim。每个值都认为是一张货币，即便是值相同的货币也认为每一张都是不同的，返回组成aim的方法数例如：arr = {1,1,1}，aim = 2第0个和第1个能组成2，第1个和第2个能组成2，第0个和第2个能组成2一共就3种方法，所以返回3
- 习题16 arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。每个值都认为是一种面值，且认为张数是无限的。返回组成aim的方法数例如：arr = {1,2}，aim = 4方法如下：1+1+1+1、1+1+2、2+2一共就3种方法，所以返回3
- 习题17 arr是货币数组，其中的值都是正数。再给定一个正数aim。每个值都认为是一张货币，认为值相同的货币没有任何不同，返回组成aim的方法数例如：arr = {1,2,1,1,2,1,2}，aim = 4方法：1+1+1+1、1+1+2、2+2一共就3种方法，所以返回3
- 习题18 给定5个参数，N，M，row，col，k表示在N*M的区域上，醉汉Bob初始在(row,col)位置Bob一共要迈出k步，且每步都会等概率向上下左右四个方向走一个单位任何时候Bob只要离开N*M的区域，就直接死亡返回k步之后，Bob还在N*M的区域的概率
- 习题19 给定3个参数，N，M，K怪兽有N滴血，等着英雄来砍自己英雄每一次打击，都会让怪兽流失[0～M]的血量到底流失多少？每一次在[0～M]上等概率的获得一个值求K次打击之后，英雄把怪兽砍死的概率
- 习题20 arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。每个值都认为是一种面值，且认为张数是无限的。返回组成aim的最少货币数
- 习题21 给定一个正数n，求n的裂开方法数，规定：后面的数不能比前面的数小比如4的裂开方法有：1+1+1+1、1+1+2、1+3、2+2、45种，所以返回5
- 习题22 给定一个正数数组arr，请把arr中所有的数分成两个集合，尽量让两个集合的累加和接近返回：最接近的情况下，较小集合的累加和
- 习题23 给定一个正数数组arr，请把arr中所有的数分成两个集合如果arr长度为偶数，两个集合包含数的个数要一样多如果arr长度为奇数，两个集合包含数的个数必须只差一个请尽量让两个集合的累加和接近返回：最接近的情况下，较小集合的累加和
- 习题24 N皇后问题是指在N*N的棋盘上要摆N个皇后，要求任何两个皇后不同行、不同列， 也不在同一条斜线上给定一个整数n，返回n皇后的摆法有多少种。n=1，返回1n=2或3，2皇后和3皇后问题无论怎么摆都不行，返回0n=8，返回92
暴力递归
暴力递归就是尝试
1，把问题转化为规模缩小了的同类问题的子问题
2，有明确的不需要继续进行递归的条件(base case)
3，有当得到了子问题的结果之后的决策过程
4，不记录每一个子问题的解
习题1 打印n层汉诺塔从最左边移动到最右边的全部过程
public static void hanoi1(int n) {
leftToRight(n);
}
// 请把1~N层圆盘 从左 -> 右
public static void leftToRight(int n) {
if (n == 1) { // base case
System.out.println("Move 1 from left to right");
return;
}
leftToMid(n - 1);
System.out.println("Move " + n + " from left to right");
midToRight(n - 1);
}
// 请把1~N层圆盘 从左 -> 中
public static void leftToMid(int n) {
if (n == 1) {
System.out.println("Move 1 from left to mid");
return;
}
leftToRight(n - 1);
System.out.println("Move " + n + " from left to mid");
rightToMid(n - 1);
}
public static void rightToMid(int n) {
if (n == 1) {
System.out.println("Move 1 from right to mid");
return;
}
rightToLeft(n - 1);
System.out.println("Move " + n + " from right to mid");
leftToMid(n - 1);
}
public static void midToRight(int n) {
if (n == 1) {
System.out.println("Move 1 from mid to right");
return;
}
midToLeft(n - 1);
System.out.println("Move " + n + " from mid to right");
leftToRight(n - 1);
}
public static void midToLeft(int n) {
if (n == 1) {
System.out.println("Move 1 from mid to left");
return;
}
midToRight(n - 1);
System.out.println("Move " + n + " from mid to left");
rightToLeft(n - 1);
}
public static void rightToLeft(int n) {
if (n == 1) {
System.out.println("Move 1 from right to left");
return;
}
rightToMid(n - 1);
System.out.println("Move " + n + " from right to left");
midToLeft(n - 1);
}
public static void hanoi2(int n) {
if (n > 0) {
func(n, "left", "right", "mid");
}
}
public static void func(int N, String from, String to, String other) {
if (N == 1) { // base
System.out.println("Move 1 from " + from + " to " + to);
} else {
func(N - 1, from, other, to);
System.out.println("Move " + N + " from " + from + " to " + to);
func(N - 1, other, to, from);
}
}
public static class Record {
public boolean finish1;
public int base;
public String from;
public String to;
public String other;
public Record(boolean f1, int b, String f, String t, String o) {
finish1 = false;
base = b;
from = f;
to = t;
other = o;
}
}
public static void hanoi3(int N) {
if (N < 1) {
return;
}
Stack<Record> stack = new Stack<>();
stack.add(new Record(false, N, "left", "right", "mid"));
while (!stack.isEmpty()) {
Record cur = stack.pop();
if (cur.base == 1) {
System.out.println("Move 1 from " + cur.from + " to " + cur.to);
if (!stack.isEmpty()) {
stack.peek().finish1 = true;
}
} else {
if (!cur.finish1) {
stack.push(cur);
stack.push(new Record(false, cur.base - 1, cur.from, cur.other, cur.to));
} else {
System.out.println("Move " + cur.base + " from " + cur.from + " to " + cur.to);
stack.push(new Record(false, cur.base - 1, cur.other, cur.to, cur.from));
}
}
}
}
public static void main(String[] args) {
int n = 3;
hanoi1(n);
System.out.println("============");
hanoi2(n);
// System.out.println("============");
// hanoi3(n);
}
习题2 给你一个栈，请你逆序这个栈，不能申请额外的数据结构，只能使用递归函数。 如何实现?
public static void reverse(Stack<Integer> stack) {
if (stack.isEmpty()) {
return;
}
int i = f(stack);
reverse(stack);
stack.push(i);
}
// 栈底元素移除掉
// 上面的元素盖下来
// 返回移除掉的栈底元素
public static int f(Stack<Integer> stack) {
int result = stack.pop();
if (stack.isEmpty()) {
return result;
} else {
int last = f(stack);
stack.push(result);
return last;
}
}
public static void main(String[] args) {
Stack<Integer> test = new Stack<Integer>();
test.push(1);
test.push(2);
test.push(3);
test.push(4);
test.push(5);
reverse(test);
while (!test.isEmpty()) {
System.out.println(test.pop());
}
}
习题3 打印一个字符串的全部子序列，要求不要出现重复的排列
// s -> "abc" ->
public static List<String> subs(String s) {
char[] str = s.toCharArray();
String path = "";
List<String> ans = new ArrayList<>();
process1(str, 0, ans, path);
return ans;
}
// str 固定参数
// 来到了str[index]字符，index是位置
// str[0..index-1]已经走过了！之前的决定，都在path上
// 之前的决定已经不能改变了，就是path
// str[index....]还能决定，之前已经确定，而后面还能自由选择的话，
// 把所有生成的子序列，放入到ans里去
public static void process1(char[] str, int index, List<String> ans, String path) {
if (index == str.length) {
ans.add(path);
return;
}
// 没有要index位置的字符
process1(str, index + 1, ans, path);
// 要了index位置的字符
process1(str, index + 1, ans, path + String.valueOf(str[index]));
}
public static List<String> subsNoRepeat(String s) {
char[] str = s.toCharArray();
String path = "";
HashSet<String> set = new HashSet<>();
process2(str, 0, set, path);
List<String> ans = new ArrayList<>();
for (String cur : set) {
ans.add(cur);
}
return ans;
}
public static void process2(char[] str, int index, HashSet<String> set, String path) {
if (index == str.length) {
set.add(path);
return;
}
String no = path;
process2(str, index + 1, set, no);
String yes = path + String.valueOf(str[index]);
process2(str, index + 1, set, yes);
}
public static void main(String[] args) {
String test = "acccc";
List<String> ans1 = subs(test);
List<String> ans2 = subsNoRepeat(test);
for (String str : ans1) {
System.out.println(str);
}
System.out.println("=================");
for (String str : ans2) {
System.out.println(str);
}
System.out.println("=================");
}
习题4 打印一个字符串的全部排列，要求不要出现重复的排列
public static List<String> permutation1(String s) {
List<String> ans = new ArrayList<>();
if (s == null || s.length() == 0) {
return ans;
}
char[] str = s.toCharArray();
ArrayList<Character> rest = new ArrayList<Character>();
for (char cha : str) {
rest.add(cha);
}
String path = "";
f(rest, path, ans);
return ans;
}
public static void f(ArrayList<Character> rest, String path, List<String> ans) {
if (rest.isEmpty()) {
ans.add(path);
} else {
int N = rest.size();
for (int i = 0; i < N; i++) {
char cur = rest.get(i);
rest.remove(i);
f(rest, path + cur, ans);
rest.add(i, cur);
}
}
}
public static List<String> permutation2(String s) {
List<String> ans = new ArrayList<>();
if (s == null || s.length() == 0) {
return ans;
}
char[] str = s.toCharArray();
g1(str, 0, ans);
return ans;
}
public static void g1(char[] str, int index, List<String> ans) {
if (index == str.length) {
ans.add(String.valueOf(str));
} else {
for (int i = index; i < str.length; i++) {
swap(str, index, i);
g1(str, index + 1, ans);
swap(str, index, i);
}
}
}
public static List<String> permutation3(String s) {
List<String> ans = new ArrayList<>();
if (s == null || s.length() == 0) {
return ans;
}
char[] str = s.toCharArray();
g2(str, 0, ans);
return ans;
}
public static void g2(char[] str, int index, List<String> ans) {
if (index == str.length) {
ans.add(String.valueOf(str));
} else {
boolean[] visited = new boolean[256];
for (int i = index; i < str.length; i++) {
if (!visited[str[i]]) {
visited[str[i]] = true;
swap(str, index, i);
g2(str, index + 1, ans);
swap(str, index, i);
}
}
}
}
public static void swap(char[] chs, int i, int j) {
char tmp = chs[i];
chs[i] = chs[j];
chs[j] = tmp;
}
public static void main(String[] args) {
String s = "acc";
List<String> ans1 = permutation1(s);
for (String str : ans1) {
System.out.println(str);
}
System.out.println("=======");
List<String> ans2 = permutation2(s);
for (String str : ans2) {
System.out.println(str);
}
System.out.println("=======");
List<String> ans3 = permutation3(s);
for (String str : ans3) {
System.out.println(str);
}
}
动态优化
1.什么暴力递归可以继续优化？
有重复调用同一个子问题的解，这种递归可以优化
如果每一个子问题都是不同的解，无法优化也不用优化
2.暴力递归和动态规划的关系
某一个暴力递归，有解的重复调用，就可以把这个暴力递归优化成动态规划
任何动态规划问题，都一定对应着某一个有重复过程的暴力递归
但不是所有的暴力递归，都一定对应着动态规划
3.如何找到某个问题的动态规划方式？
1）设计暴力递归：重要原则+4种常见尝试模型！重点！
2）分析有没有重复解：套路解决
3）用记忆化搜索 -> 用严格表结构实现动态规划：套路解决
4）看看能否继续优化：套路解决
4.面试中设计暴力递归过程的原则
1）每一个可变参数的类型，一定不要比int类型更加复杂
2）原则1）可以违反，让类型突破到一维线性结构，那必须是单一可变参数
3）如果发现原则1）被违反，但不违反原则2），只需要做到记忆化搜索即可
4）可变参数的个数，能少则少
5.常见的4种尝试模型
1）从左往右的尝试模型
2）范围上的尝试模型
3）多样本位置全对应的尝试模型
4）寻找业务限制的尝试模型
习题5 假设有排成一行的N个位置，记为1~N，N 一定大于或等于 2开始时机器人在其中的M位置上(M 一定是 1~N 中的一个)如果机器人来到1位置，那么下一步只能往右来到2位置；如果机器人来到N位置，那么下一步只能往左来到 N-1 位置；如果机器人来到中间位置，那么下一步可以往左走或者往右走；规定机器人必须走 K 步，最终能来到P位置(P也是1~N中的一个)的方法有多少种给定四个参数 N、M、K、P，返回方法数。
public static int ways1(int N, int start, int aim, int K) {
if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
return -1;
}
return process1(start, K, aim, N);
}
// 机器人当前来到的位置是cur，
// 机器人还有rest步需要去走，
// 最终的目标是aim，
// 有哪些位置？1~N
// 返回：机器人从cur出发，走过rest步之后，最终停在aim的方法数，是多少？
public static int process1(int cur, int rest, int aim, int N) {
if (rest == 0) { // 如果已经不需要走了，走完了！
return cur == aim ? 1 : 0;
}
// (cur, rest)
if (cur == 1) { // 1 -> 2
return process1(2, rest - 1, aim, N);
}
// (cur, rest)
if (cur == N) { // N-1 <- N
return process1(N - 1, rest - 1, aim, N);
}
// (cur, rest)
return process1(cur - 1, rest - 1, aim, N) + process1(cur + 1, rest - 1, aim, N);
}
public static int ways2(int N, int start, int aim, int K) {
if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
return -1;
}
int[][] dp = new int[N + 1][K + 1];
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= K; j++) {
dp[i][j] = -1;
}
}
// dp就是缓存表
// dp[cur][rest] == -1 -> process1(cur, rest)之前没算过！
// dp[cur][rest] != -1 -> process1(cur, rest)之前算过！返回值，dp[cur][rest]
// N+1 * K+1
return process2(start, K, aim, N, dp);
}
// cur 范: 1 ~ N
// rest 范：0 ~ K
public static int process2(int cur, int rest, int aim, int N, int[][] dp) {
if (dp[cur][rest] != -1) {
return dp[cur][rest];
}
// 之前没算过！
int ans = 0;
if (rest == 0) {
ans = cur == aim ? 1 : 0;
} else if (cur == 1) {
ans = process2(2, rest - 1, aim, N, dp);
} else if (cur == N) {
ans = process2(N - 1, rest - 1, aim, N, dp);
} else {
ans = process2(cur - 1, rest - 1, aim, N, dp) + process2(cur + 1, rest - 1, aim, N, dp);
}
dp[cur][rest] = ans;
return ans;
}
public static int ways3(int N, int start, int aim, int K) {
if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
return -1;
}
int[][] dp = new int[N + 1][K + 1];
dp[aim][0] = 1;
for (int rest = 1; rest <= K; rest++) {
dp[1][rest] = dp[2][rest - 1];
for (int cur = 2; cur < N; cur++) {
dp[cur][rest] = dp[cur - 1][rest - 1] + dp[cur + 1][rest - 1];
}
dp[N][rest] = dp[N - 1][rest - 1];
}
return dp[start][K];
}
public static void main(String[] args) {
System.out.println(ways1(5, 2, 4, 6));
System.out.println(ways2(5, 2, 4, 6));
System.out.println(ways3(5, 2, 4, 6));
}
习题6 给定一个整型数组arr，代表数值不同的纸牌排成一条线玩家A和玩家B依次拿走每张纸牌规定玩家A先拿，玩家B后拿但是每个玩家每次只能拿走最左或最右的纸牌玩家A和玩家B都绝顶聪明请返回最后获胜者的分数。
// 根据规则，返回获胜者的分数
public static int win1(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int first = f1(arr, 0, arr.length - 1);
int second = g1(arr, 0, arr.length - 1);
return Math.max(first, second);
}
// arr[L..R]，先手获得的最好分数返回
public static int f1(int[] arr, int L, int R) {
if (L == R) {
return arr[L];
}
int p1 = arr[L] + g1(arr, L + 1, R);
int p2 = arr[R] + g1(arr, L, R - 1);
return Math.max(p1, p2);
}
// // arr[L..R]，后手获得的最好分数返回
public static int g1(int[] arr, int L, int R) {
if (L == R) {
return 0;
}
int p1 = f1(arr, L + 1, R); // 对手拿走了L位置的数
int p2 = f1(arr, L, R - 1); // 对手拿走了R位置的数
return Math.min(p1, p2);
}
public static int win2(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int N = arr.length;
int[][] fmap = new int[N][N];
int[][] gmap = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
fmap[i][j] = -1;
gmap[i][j] = -1;
}
}
int first = f2(arr, 0, arr.length - 1, fmap, gmap);
int second = g2(arr, 0, arr.length - 1, fmap, gmap);
return Math.max(first, second);
}
// arr[L..R]，先手获得的最好分数返回
public static int f2(int[] arr, int L, int R, int[][] fmap, int[][] gmap) {
if (fmap[L][R] != -1) {
return fmap[L][R];
}
int ans = 0;
if (L == R) {
ans = arr[L];
} else {
int p1 = arr[L] + g2(arr, L + 1, R, fmap, gmap);
int p2 = arr[R] + g2(arr, L, R - 1, fmap, gmap);
ans = Math.max(p1, p2);
}
fmap[L][R] = ans;
return ans;
}
// // arr[L..R]，后手获得的最好分数返回
public static int g2(int[] arr, int L, int R, int[][] fmap, int[][] gmap) {
if (gmap[L][R] != -1) {
return gmap[L][R];
}
int ans = 0;
if (L != R) {
int p1 = f2(arr, L + 1, R, fmap, gmap); // 对手拿走了L位置的数
int p2 = f2(arr, L, R - 1, fmap, gmap); // 对手拿走了R位置的数
ans = Math.min(p1, p2);
}
gmap[L][R] = ans;
return ans;
}
public static int win3(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int N = arr.length;
int[][] fmap = new int[N][N];
int[][] gmap = new int[N][N];
for (int i = 0; i < N; i++) {
fmap[i][i] = arr[i];
}
for (int startCol = 1; startCol < N; startCol++) {
int L = 0;
int R = startCol;
while (R < N) {
fmap[L][R] = Math.max(arr[L] + gmap[L + 1][R], arr[R] + gmap[L][R - 1]);
gmap[L][R] = Math.min(fmap[L + 1][R], fmap[L][R - 1]);
L++;
R++;
}
}
return Math.max(fmap[0][N - 1], gmap[0][N - 1]);
}
public static void main(String[] args) {
int[] arr = { 5, 7, 4, 5, 8, 1, 6, 0, 3, 4, 6, 1, 7 };
System.out.println(win1(arr));
System.out.println(win2(arr));
System.out.println(win3(arr));
}
习题7 给定两个长度都为N的数组weights和values，weights[i]和values[i]分别代表 i号物品的重量和价值。给定一个正数bag，表示一个载重bag的袋子，你装的物品不能超过这个重量。返回你能装下最多的价值是多少?
// 所有的货，重量和价值，都在w和v数组里
// 为了方便，其中没有负数
// bag背包容量，不能超过这个载重
// 返回：不超重的情况下，能够得到的最大价值
public static int maxValue(int[] w, int[] v, int bag) {
if (w == null || v == null || w.length != v.length || w.length == 0) {
return 0;
}
// 尝试函数！
return process(w, v, 0, bag);
}
// index 0~N
// rest 负~bag
public static int process(int[] w, int[] v, int index, int rest) {
if (rest < 0) {
return -1;
}
if (index == w.length) {
return 0;
}
int p1 = process(w, v, index + 1, rest);
int p2 = 0;
int next = process(w, v, index + 1, rest - w[index]);
if (next != -1) {
p2 = v[index] + next;
}
return Math.max(p1, p2);
}
public static int dp(int[] w, int[] v, int bag) {
if (w == null || v == null || w.length != v.length || w.length == 0) {
return 0;
}
int N = w.length;
int[][] dp = new int[N + 1][bag + 1];
for (int index = N - 1; index >= 0; index--) {
for (int rest = 0; rest <= bag; rest++) {
int p1 = dp[index + 1][rest];
int p2 = 0;
int next = rest - w[index] < 0 ? -1 : dp[index + 1][rest - w[index]];
if (next != -1) {
p2 = v[index] + next;
}
dp[index][rest] = Math.max(p1, p2);
}
}
return dp[0][bag];
}
public static void main(String[] args) {
int[] weights = { 3, 2, 4, 7, 3, 1, 7 };
int[] values = { 5, 6, 3, 19, 12, 4, 2 };
int bag = 15;
System.out.println(maxValue(weights, values, bag));
System.out.println(dp(weights, values, bag));
}
习题8 规定1和A对应、2和B对应、3和C对应…26和Z对应那么一个数字字符串比如"111”就可以转化为:“AAA”、"KA"和"AK"给定一个只有数字字符组成的字符串str，返回有多少种转化结果
// str只含有数字字符0~9
// 返回多少种转化方案
public static int number(String str) {
if (str == null || str.length() == 0) {
return 0;
}
return process(str.toCharArray(), 0);
}
// str[0..i-1]转化无需过问
// str[i.....]去转化，返回有多少种转化方法
public static int process(char[] str, int i) {
if (i == str.length) {
return 1;
}
// i没到最后，说明有字符
if (str[i] == '0') { // 之前的决定有问题
return 0;
}
// str[i] != '0'
// 可能性一，i单转
int ways = process(str, i + 1);
if (i + 1 < str.length && (str[i] - '0') * 10 + str[i + 1] - '0' < 27) {
ways += process(str, i + 2);
}
return ways;
}
// 从右往左的动态规划
// 就是上面方法的动态规划版本
// dp[i]表示：str[i...]有多少种转化方式
public static int dp1(String s) {
if (s == null || s.length() == 0) {
return 0;
}
char[] str = s.toCharArray();
int N = str.length;
int[] dp = new int[N + 1];
dp[N] = 1;
for (int i = N - 1; i >= 0; i--) {
if (str[i] != '0') {
int ways = dp[i + 1];
if (i + 1 < str.length && (str[i] - '0') * 10 + str[i + 1] - '0' < 27) {
ways += dp[i + 2];
}
dp[i] = ways;
}
}
return dp[0];
}
// 从左往右的动态规划
// dp[i]表示：str[0...i]有多少种转化方式
public static int dp2(String s) {
if (s == null || s.length() == 0) {
return 0;
}
char[] str = s.toCharArray();
int N = str.length;
if (str[0] == '0') {
return 0;
}
int[] dp = new int[N];
dp[0] = 1;
for (int i = 1; i < N; i++) {
if (str[i] == '0') {
// 如果此时str[i]=='0'，那么他是一定要拉前一个字符(i-1的字符)一起拼的，
// 那么就要求前一个字符，不能也是‘0’，否则拼不了。
// 前一个字符不是‘0’就够了嘛？不够，还得要求拼完了要么是10，要么是20，如果更大的话，拼不了。
// 这就够了嘛？还不够，你们拼完了，还得要求str[0...i-2]真的可以被分解！
// 如果str[0...i-2]都不存在分解方案，那i和i-1拼成了也不行，因为之前的搞定不了。
if (str[i - 1] == '0' || str[i - 1] > '2' || (i - 2 >= 0 && dp[i - 2] == 0)) {
return 0;
} else {
dp[i] = i - 2 >= 0 ? dp[i - 2] : 1;
}
} else {
dp[i] = dp[i - 1];
if (str[i - 1] != '0' && (str[i - 1] - '0') * 10 + str[i] - '0' <= 26) {
dp[i] += i - 2 >= 0 ? dp[i - 2] : 1;
}
}
}
return dp[N - 1];
}
// 为了测试
public static String randomString(int len) {
char[] str = new char[len];
for (int i = 0; i < len; i++) {
str[i] = (char) ((int) (Math.random() * 10) + '0');
}
return String.valueOf(str);
}
// 为了测试
public static void main(String[] args) {
int N = 30;
int testTime = 1000000;
System.out.println("测试开始");
for (int i = 0; i < testTime; i++) {
int len = (int) (Math.random() * N);
String s = randomString(len);
int ans0 = number(s);
int ans1 = dp1(s);
int ans2 = dp2(s);
if (ans0 != ans1 || ans0 != ans2) {
System.out.println(s);
System.out.println(ans0);
System.out.println(ans1);
System.out.println(ans2);
System.out.println("Oops!");
break;
}
}
System.out.println("测试结束");
}
习题9 给定一个字符串str，给定一个字符串类型的数组arr，出现的字符都是小写英文arr每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来返回需要至少多少张贴纸可以完成这个任务。例子：str= “babac”，arr = {“ba”,“c”,“abcd”}ba + ba + c 3 abcd + abcd 2 abcd+ba 2所以返回2
public static int minStickers1(String[] stickers, String target) {
int ans = process1(stickers, target);
return ans == Integer.MAX_VALUE ? -1 : ans;
}
// 所有贴纸stickers，每一种贴纸都有无穷张
// target
// 最少张数
public static int process1(String[] stickers, String target) {
if (target.length() == 0) {
return 0;
}
int min = Integer.MAX_VALUE;
for (String first : stickers) {
String rest = minus(target, first);
if (rest.length() != target.length()) {
min = Math.min(min, process1(stickers, rest));
}
}
return min + (min == Integer.MAX_VALUE ? 0 : 1);
}
public static String minus(String s1, String s2) {
char[] str1 = s1.toCharArray();
char[] str2 = s2.toCharArray();
int[] count = new int[26];
for (char cha : str1) {
count[cha - 'a']++;
}
for (char cha : str2) {
count[cha - 'a']--;
}
StringBuilder builder = new StringBuilder();
for (int i = 0; i < 26; i++) {
if (count[i] > 0) {
for (int j = 0; j < count[i]; j++) {
builder.append((char) (i + 'a'));
}
}
}
return builder.toString();
}
public static int minStickers2(String[] stickers, String target) {
int N = stickers.length;
// 关键优化(用词频表替代贴纸数组)
int[][] counts = new int[N][26];
for (int i = 0; i < N; i++) {
char[] str = stickers[i].toCharArray();
for (char cha : str) {
counts[i][cha - 'a']++;
}
}
int ans = process2(counts, target);
return ans == Integer.MAX_VALUE ? -1 : ans;
}
// stickers[i] 数组，当初i号贴纸的字符统计 int[][] stickers -> 所有的贴纸
// 每一种贴纸都有无穷张
// 返回搞定target的最少张数
// 最少张数
public static int process2(int[][] stickers, String t) {
if (t.length() == 0) {
return 0;
}
// target做出词频统计
// target aabbc 2 2 1..
// 0 1 2..
char[] target = t.toCharArray();
int[] tcounts = new int[26];
for (char cha : target) {
tcounts[cha - 'a']++;
}
int N = stickers.length;
int min = Integer.MAX_VALUE;
for (int i = 0; i < N; i++) {
// 尝试第一张贴纸是谁
int[] sticker = stickers[i];
// 最关键的优化(重要的剪枝!这一步也是贪心!)
if (sticker[target[0] - 'a'] > 0) {
StringBuilder builder = new StringBuilder();
for (int j = 0; j < 26; j++) {
if (tcounts[j] > 0) {
int nums = tcounts[j] - sticker[j];
for (int k = 0; k < nums; k++) {
builder.append((char) (j + 'a'));
}
}
}
String rest = builder.toString();
min = Math.min(min, process2(stickers, rest));
}
}
return min + (min == Integer.MAX_VALUE ? 0 : 1);
}
public static int minStickers3(String[] stickers, String target) {
int N = stickers.length;
int[][] counts = new int[N][26];
for (int i = 0; i < N; i++) {
char[] str = stickers[i].toCharArray();
for (char cha : str) {
counts[i][cha - 'a']++;
}
}
HashMap<String, Integer> dp = new HashMap<>();
dp.put("", 0);
int ans = process3(counts, target, dp);
return ans == Integer.MAX_VALUE ? -1 : ans;
}
public static int process3(int[][] stickers, String t, HashMap<String, Integer> dp) {
if (dp.containsKey(t)) {
return dp.get(t);
}
char[] target = t.toCharArray();
int[] tcounts = new int[26];
for (char cha : target) {
tcounts[cha - 'a']++;
}
int N = stickers.length;
int min = Integer.MAX_VALUE;
for (int i = 0; i < N; i++) {
int[] sticker = stickers[i];
if (sticker[target[0] - 'a'] > 0) {
StringBuilder builder = new StringBuilder();
for (int j = 0; j < 26; j++) {
if (tcounts[j] > 0) {
int nums = tcounts[j] - sticker[j];
for (int k = 0; k < nums; k++) {
builder.append((char) (j + 'a'));
}
}
}
String rest = builder.toString();
min = Math.min(min, process3(stickers, rest, dp));
}
}
int ans = min + (min == Integer.MAX_VALUE ? 0 : 1);
dp.put(t, ans);
return ans;
}
习题10 给定两个字符串str1和str2，返回这两个字符串的最长公共子序列长度比如 ： str1 = “a12b3c456d”,str2 = “1ef23ghi4j56k”最长公共子序列是“123456”，所以返回长度6
public static int longestCommonSubsequence1(String s1, String s2) {
if (s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0) {
return 0;
}
char[] str1 = s1.toCharArray();
char[] str2 = s2.toCharArray();
// 尝试
return process1(str1, str2, str1.length - 1, str2.length - 1);
}
// str1[0...i]和str2[0...j]，这个范围上最长公共子序列长度是多少？
// 可能性分类:
// a) 最长公共子序列，一定不以str1[i]字符结尾、也一定不以str2[j]字符结尾
// b) 最长公共子序列，可能以str1[i]字符结尾、但是一定不以str2[j]字符结尾
// c) 最长公共子序列，一定不以str1[i]字符结尾、但是可能以str2[j]字符结尾
// d) 最长公共子序列，必须以str1[i]字符结尾、也必须以str2[j]字符结尾
// 注意：a)、b)、c)、d)并不是完全互斥的，他们可能会有重叠的情况
// 但是可以肯定，答案不会超过这四种可能性的范围
// 那么我们分别来看一下，这几种可能性怎么调用后续的递归。
// a) 最长公共子序列，一定不以str1[i]字符结尾、也一定不以str2[j]字符结尾
// 如果是这种情况，那么有没有str1[i]和str2[j]就根本不重要了，因为这两个字符一定没用啊
// 所以砍掉这两个字符，最长公共子序列 = str1[0...i-1]与str2[0...j-1]的最长公共子序列长度(后续递归)
// b) 最长公共子序列，可能以str1[i]字符结尾、但是一定不以str2[j]字符结尾
// 如果是这种情况，那么我们可以确定str2[j]一定没有用，要砍掉；但是str1[i]可能有用，所以要保留
// 所以，最长公共子序列 = str1[0...i]与str2[0...j-1]的最长公共子序列长度(后续递归)
// c) 最长公共子序列，一定不以str1[i]字符结尾、但是可能以str2[j]字符结尾
// 跟上面分析过程类似，最长公共子序列 = str1[0...i-1]与str2[0...j]的最长公共子序列长度(后续递归)
// d) 最长公共子序列，必须以str1[i]字符结尾、也必须以str2[j]字符结尾
// 同时可以看到，可能性d)存在的条件，一定是在str1[i] == str2[j]的情况下，才成立的
// 所以，最长公共子序列总长度 = str1[0...i-1]与str2[0...j-1]的最长公共子序列长度(后续递归) + 1(共同的结尾)
// 综上，四种情况已经穷尽了所有可能性。四种情况中取最大即可
// 其中b)、c)一定参与最大值的比较，
// 当str1[i] == str2[j]时，a)一定比d)小，所以d)参与
// 当str1[i] != str2[j]时，d)压根不存在，所以a)参与
// 但是再次注意了！
// a)是：str1[0...i-1]与str2[0...j-1]的最长公共子序列长度
// b)是：str1[0...i]与str2[0...j-1]的最长公共子序列长度
// c)是：str1[0...i-1]与str2[0...j]的最长公共子序列长度
// a)中str1的范围 < b)中str1的范围，a)中str2的范围 == b)中str2的范围
// 所以a)不用求也知道，它比不过b)啊，因为有一个样本的范围比b)小啊！
// a)中str1的范围 == c)中str1的范围，a)中str2的范围 < c)中str2的范围
// 所以a)不用求也知道，它比不过c)啊，因为有一个样本的范围比c)小啊！
// 至此，可以知道，a)就是个垃圾，有它没它，都不影响最大值的决策
// 所以，当str1[i] == str2[j]时，b)、c)、d)中选出最大值
// 当str1[i] != str2[j]时，b)、c)中选出最大值
public static int process1(char[] str1, char[] str2, int i, int j) {
if (i == 0 && j == 0) {
// str1[0..0]和str2[0..0]，都只剩一个字符了
// 那如果字符相等，公共子序列长度就是1，不相等就是0
// 这显而易见
return str1[i] == str2[j] ? 1 : 0;
} else if (i == 0) {
// 这里的情况为：
// str1[0...0]和str2[0...j]，str1只剩1个字符了，但是str2不只一个字符
// 因为str1只剩一个字符了，所以str1[0...0]和str2[0...j]公共子序列最多长度为1
// 如果str1[0] == str2[j]，那么此时相等已经找到了！公共子序列长度就是1，也不可能更大了
// 如果str1[0] != str2[j]，只是此时不相等而已，
// 那么str2[0...j-1]上有没有字符等于str1[0]呢？不知道，所以递归继续找
if (str1[i] == str2[j]) {
return 1;
} else {
return process1(str1, str2, i, j - 1);
}
} else if (j == 0) {
// 和上面的else if同理
// str1[0...i]和str2[0...0]，str2只剩1个字符了，但是str1不只一个字符
// 因为str2只剩一个字符了，所以str1[0...i]和str2[0...0]公共子序列最多长度为1
// 如果str1[i] == str2[0]，那么此时相等已经找到了！公共子序列长度就是1，也不可能更大了
// 如果str1[i] != str2[0]，只是此时不相等而已，
// 那么str1[0...i-1]上有没有字符等于str2[0]呢？不知道，所以递归继续找
if (str1[i] == str2[j]) {
return 1;
} else {
return process1(str1, str2, i - 1, j);
}
} else { // i != 0 && j != 0
// 这里的情况为：
// str1[0...i]和str2[0...i]，str1和str2都不只一个字符
// 看函数开始之前的注释部分
// p1就是可能性c)
int p1 = process1(str1, str2, i - 1, j);
// p2就是可能性b)
int p2 = process1(str1, str2, i, j - 1);
// p3就是可能性d)，如果可能性d)存在，即str1[i] == str2[j]，那么p3就求出来，参与pk
// 如果可能性d)不存在，即str1[i] != str2[j]，那么让p3等于0，然后去参与pk，反正不影响
int p3 = str1[i] == str2[j] ? (1 + process1(str1, str2, i - 1, j - 1)) : 0;
return Math.max(p1, Math.max(p2, p3));
}
}
public static int longestCommonSubsequence2(String s1, String s2) {
if (s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0) {
return 0;
}
char[] str1 = s1.toCharArray();
char[] str2 = s2.toCharArray();
int N = str1.length;
int M = str2.length;
int[][] dp = new int[N][M];
dp[0][0] = str1[0] == str2[0] ? 1 : 0;
for (int j = 1; j < M; j++) {
dp[0][j] = str1[0] == str2[j] ? 1 : dp[0][j - 1];
}
for (int i = 1; i < N; i++) {
dp[i][0] = str1[i] == str2[0] ? 1 : dp[i - 1][0];
}
for (int i = 1; i < N; i++) {
for (int j = 1; j < M; j++) {
int p1 = dp[i - 1][j];
int p2 = dp[i][j - 1];
int p3 = str1[i] == str2[j] ? (1 + dp[i - 1][j - 1]) : 0;
dp[i][j] = Math.max(p1, Math.max(p2, p3));
}
}
return dp[N - 1][M - 1];
}
习题11 给定一个字符串str，返回这个字符串的最长回文子序列长度比如 ： str = “a12b3c43def2ghi1kpm”最长回文子序列是“1234321”或者“123c321”，返回长度7
public static int lpsl1(String s) {
if (s == null || s.length() == 0) {
return 0;
}
char[] str = s.toCharArray();
return f(str, 0, str.length - 1);
}
// str[L..R]最长回文子序列长度返回
public static int f(char[] str, int L, int R) {
if (L == R) {
return 1;
}
if (L == R - 1) {
return str[L] == str[R] ? 2 : 1;
}
int p1 = f(str, L + 1, R - 1);
int p2 = f(str, L, R - 1);
int p3 = f(str, L + 1, R);
int p4 = str[L] != str[R] ? 0 : (2 + f(str, L + 1, R - 1));
return Math.max(Math.max(p1, p2), Math.max(p3, p4));
}
public static int lpsl2(String s) {
if (s == null || s.length() == 0) {
return 0;
}
char[] str = s.toCharArray();
int N = str.length;
int[][] dp = new int[N][N];
dp[N - 1][N - 1] = 1;
for (int i = 0; i < N - 1; i++) {
dp[i][i] = 1;
dp[i][i + 1] = str[i] == str[i + 1] ? 2 : 1;
}
for (int L = N - 3; L >= 0; L--) {
for (int R = L + 2; R < N; R++) {
dp[L][R] = Math.max(dp[L][R - 1], dp[L + 1][R]);
if (str[L] == str[R]) {
dp[L][R] = Math.max(dp[L][R], 2 + dp[L + 1][R - 1]);
}
}
}
return dp[0][N - 1];
}
public static int longestPalindromeSubseq1(String s) {
if (s == null || s.length() == 0) {
return 0;
}
if (s.length() == 1) {
return 1;
}
char[] str = s.toCharArray();
char[] reverse = reverse(str);
return longestCommonSubsequence(str, reverse);
}
public static char[] reverse(char[] str) {
int N = str.length;
char[] reverse = new char[str.length];
for (int i = 0; i < str.length; i++) {
reverse[--N] = str[i];
}
return reverse;
}
public static int longestCommonSubsequence(char[] str1, char[] str2) {
int N = str1.length;
int M = str2.length;
int[][] dp = new int[N][M];
dp[0][0] = str1[0] == str2[0] ? 1 : 0;
for (int i = 1; i < N; i++) {
dp[i][0] = str1[i] == str2[0] ? 1 : dp[i - 1][0];
}
for (int j = 1; j < M; j++) {
dp[0][j] = str1[0] == str2[j] ? 1 : dp[0][j - 1];
}
for (int i = 1; i < N; i++) {
for (int j = 1; j < M; j++) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
if (str1[i] == str2[j]) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
}
}
}
return dp[N - 1][M - 1];
}
public static int longestPalindromeSubseq2(String s) {
if (s == null || s.length() == 0) {
return 0;
}
if (s.length() == 1) {
return 1;
}
char[] str = s.toCharArray();
int N = str.length;
int[][] dp = new int[N][N];
dp[N - 1][N - 1] = 1;
for (int i = 0; i < N - 1; i++) {
dp[i][i] = 1;
dp[i][i + 1] = str[i] == str[i + 1] ? 2 : 1;
}
for (int i = N - 3; i >= 0; i--) {
for (int j = i + 2; j < N; j++) {
dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
if (str[i] == str[j]) {
dp[i][j] = Math.max(dp[i][j], dp[i + 1][j - 1] + 2);
}
}
}
return dp[0][N - 1];
}
习题12 请同学们自行搜索或者想象一个象棋的棋盘，然后把整个棋盘放入第一象限，棋盘的最左下角是(0,0)位置那么整个棋盘就是横坐标上9条线、纵坐标上10条线的区域给你三个 参数 x，y，k返回“马”从(0,0)位置出发，必须走k步最后落在(x,y)上的方法数有多少种?
// 当前来到的位置是（x,y）
// 还剩下rest步需要跳
// 跳完rest步，正好跳到a，b的方法数是多少？
// 10 * 9
public static int jump(int a, int b, int k) {
return process(0, 0, k, a, b);
}
public static int process(int x, int y, int rest, int a, int b) {
if (x < 0 || x > 9 || y < 0 || y > 8) {
return 0;
}
if (rest == 0) {
return (x == a && y == b) ? 1 : 0;
}
int ways = process(x + 2, y + 1, rest - 1, a, b);
ways += process(x + 1, y + 2, rest - 1, a, b);
ways += process(x - 1, y + 2, rest - 1, a, b);
ways += process(x - 2, y + 1, rest - 1, a, b);
ways += process(x - 2, y - 1, rest - 1, a, b);
ways += process(x - 1, y - 2, rest - 1, a, b);
ways += process(x + 1, y - 2, rest - 1, a, b);
ways += process(x + 2, y - 1, rest - 1, a, b);
return ways;
}
public static int dp(int a, int b, int k) {
int[][][] dp = new int[10][9][k + 1];
dp[a][b][0] = 1;
for (int rest = 1; rest <= k; rest++) {
for (int x = 0; x < 10; x++) {
for (int y = 0; y < 9; y++) {
int ways = pick(dp, x + 2, y + 1, rest - 1);
ways += pick(dp, x + 1, y + 2, rest - 1);
ways += pick(dp, x - 1, y + 2, rest - 1);
ways += pick(dp, x - 2, y + 1, rest - 1);
ways += pick(dp, x - 2, y - 1, rest - 1);
ways += pick(dp, x - 1, y - 2, rest - 1);
ways += pick(dp, x + 1, y - 2, rest - 1);
ways += pick(dp, x + 2, y - 1, rest - 1);
dp[x][y][rest] = ways;
}
}
}
return dp[0][0][k];
}
public static int pick(int[][][] dp, int x, int y, int rest) {
if (x < 0 || x > 9 || y < 0 || y > 8) {
return 0;
}
return dp[x][y][rest];
}
public static int ways(int a, int b, int step) {
return f(0, 0, step, a, b);
}
public static int f(int i, int j, int step, int a, int b) {
if (i < 0 || i > 9 || j < 0 || j > 8) {
return 0;
}
if (step == 0) {
return (i == a && j == b) ? 1 : 0;
}
return f(i - 2, j + 1, step - 1, a, b) + f(i - 1, j + 2, step - 1, a, b) + f(i + 1, j + 2, step - 1, a, b)
+ f(i + 2, j + 1, step - 1, a, b) + f(i + 2, j - 1, step - 1, a, b) + f(i + 1, j - 2, step - 1, a, b)
+ f(i - 1, j - 2, step - 1, a, b) + f(i - 2, j - 1, step - 1, a, b);
}
public static int waysdp(int a, int b, int s) {
int[][][] dp = new int[10][9][s + 1];
dp[a][b][0] = 1;
for (int step = 1; step <= s; step++) { // 按层来
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 9; j++) {
dp[i][j][step] = getValue(dp, i - 2, j + 1, step - 1) + getValue(dp, i - 1, j + 2, step - 1)
+ getValue(dp, i + 1, j + 2, step - 1) + getValue(dp, i + 2, j + 1, step - 1)
+ getValue(dp, i + 2, j - 1, step - 1) + getValue(dp, i + 1, j - 2, step - 1)
+ getValue(dp, i - 1, j - 2, step - 1) + getValue(dp, i - 2, j - 1, step - 1);
}
}
}
return dp[0][0][s];
}
// 在dp表中，得到dp[i][j][step]的值，但如果(i，j)位置越界的话，返回0；
public static int getValue(int[][][] dp, int i, int j, int step) {
if (i < 0 || i > 9 || j < 0 || j > 8) {
return 0;
}
return dp[i][j][step];
}
public static void main(String[] args) {
int x = 7;
int y = 7;
int step = 10;
System.out.println(ways(x, y, step));
System.out.println(dp(x, y, step));
System.out.println(jump(x, y, step));
}
习题13 给定一个数组arr，arr[i]代表第i号咖啡机泡一杯咖啡的时间给定一个正数N，表示N个人等着咖啡机泡咖啡，每台咖啡机只能轮流泡咖啡只有一台咖啡机，一次只能洗一个杯子，时间耗费a，洗完才能洗下一杯每个咖啡杯也可以自己挥发干净，时间耗费b，咖啡杯可以并行挥发假设所有人拿到咖啡之后立刻喝干净，返回从开始等到所有咖啡机变干净的最短时间三个参数：int[] arr、int N，int a、int b
// 验证的方法
// 彻底的暴力
// 很慢但是绝对正确
public static int right(int[] arr, int n, int a, int b) {
int[] times = new int[arr.length];
int[] drink = new int[n];
return forceMake(arr, times, 0, drink, n, a, b);
}
// 每个人暴力尝试用每一个咖啡机给自己做咖啡
public static int forceMake(int[] arr, int[] times, int kth, int[] drink, int n, int a, int b) {
if (kth == n) {
int[] drinkSorted = Arrays.copyOf(drink, kth);
Arrays.sort(drinkSorted);
return forceWash(drinkSorted, a, b, 0, 0, 0);
}
int time = Integer.MAX_VALUE;
for (int i = 0; i < arr.length; i++) {
int work = arr[i];
int pre = times[i];
drink[kth] = pre + work;
times[i] = pre + work;
time = Math.min(time, forceMake(arr, times, kth + 1, drink, n, a, b));
drink[kth] = 0;
times[i] = pre;
}
return time;
}
public static int forceWash(int[] drinks, int a, int b, int index, int washLine, int time) {
if (index == drinks.length) {
return time;
}
// 选择一：当前index号咖啡杯，选择用洗咖啡机刷干净
int wash = Math.max(drinks[index], washLine) + a;
int ans1 = forceWash(drinks, a, b, index + 1, wash, Math.max(wash, time));
// 选择二：当前index号咖啡杯，选择自然挥发
int dry = drinks[index] + b;
int ans2 = forceWash(drinks, a, b, index + 1, washLine, Math.max(dry, time));
return Math.min(ans1, ans2);
}
// 以下为贪心+优良暴力
public static class Machine {
public int timePoint;
public int workTime;
public Machine(int t, int w) {
timePoint = t;
workTime = w;
}
}
public static class MachineComparator implements Comparator<Machine> {
@Override
public int compare(Machine o1, Machine o2) {
return (o1.timePoint + o1.workTime) - (o2.timePoint + o2.workTime);
}
}
// 优良一点的暴力尝试的方法
public static int minTime1(int[] arr, int n, int a, int b) {
PriorityQueue<Machine> heap = new PriorityQueue<Machine>(new MachineComparator());
for (int i = 0; i < arr.length; i++) {
heap.add(new Machine(0, arr[i]));
}
int[] drinks = new int[n];
for (int i = 0; i < n; i++) {
Machine cur = heap.poll();
cur.timePoint += cur.workTime;
drinks[i] = cur.timePoint;
heap.add(cur);
}
return bestTime(drinks, a, b, 0, 0);
}
// drinks 所有杯子可以开始洗的时间
// wash 单杯洗干净的时间（串行）
// air 挥发干净的时间(并行)
// free 洗的机器什么时候可用
// drinks[index.....]都变干净，最早的结束时间（返回）
public static int bestTime(int[] drinks, int wash, int air, int index, int free) {
if (index == drinks.length) {
return 0;
}
// index号杯子 决定洗
int selfClean1 = Math.max(drinks[index], free) + wash;
int restClean1 = bestTime(drinks, wash, air, index + 1, selfClean1);
int p1 = Math.max(selfClean1, restClean1);
// index号杯子 决定挥发
int selfClean2 = drinks[index] + air;
int restClean2 = bestTime(drinks, wash, air, index + 1, free);
int p2 = Math.max(selfClean2, restClean2);
return Math.min(p1, p2);
}
// 贪心+优良尝试改成动态规划
public static int minTime2(int[] arr, int n, int a, int b) {
PriorityQueue<Machine> heap = new PriorityQueue<Machine>(new MachineComparator());
for (int i = 0; i < arr.length; i++) {
heap.add(new Machine(0, arr[i]));
}
int[] drinks = new int[n];
for (int i = 0; i < n; i++) {
Machine cur = heap.poll();
cur.timePoint += cur.workTime;
drinks[i] = cur.timePoint;
heap.add(cur);
}
return bestTimeDp(drinks, a, b);
}
public static int bestTimeDp(int[] drinks, int wash, int air) {
int N = drinks.length;
int maxFree = 0;
for (int i = 0; i < drinks.length; i++) {
maxFree = Math.max(maxFree, drinks[i]) + wash;
}
int[][] dp = new int[N + 1][maxFree + 1];
for (int index = N - 1; index >= 0; index--) {
for (int free = 0; free <= maxFree; free++) {
int selfClean1 = Math.max(drinks[index], free) + wash;
if (selfClean1 > maxFree) {
break; // 因为后面的也都不用填了
}
// index号杯子 决定洗
int restClean1 = dp[index + 1][selfClean1];
int p1 = Math.max(selfClean1, restClean1);
// index号杯子 决定挥发
int selfClean2 = drinks[index] + air;
int restClean2 = dp[index + 1][free];
int p2 = Math.max(selfClean2, restClean2);
dp[index][free] = Math.min(p1, p2);
}
}
return dp[0][0];
}
// for test
public static int[] randomArray(int len, int max) {
int[] arr = new int[len];
for (int i = 0; i < len; i++) {
arr[i] = (int) (Math.random() * max) + 1;
}
return arr;
}
// for test
public static void printArray(int[] arr) {
System.out.print("arr : ");
for (int j = 0; j < arr.length; j++) {
System.out.print(arr[j] + ", ");
}
System.out.println();
}
public static void main(String[] args) {
int len = 10;
int max = 10;
int testTime = 10;
System.out.println("测试开始");
for (int i = 0; i < testTime; i++) {
int[] arr = randomArray(len, max);
int n = (int) (Math.random() * 7) + 1;
int a = (int) (Math.random() * 7) + 1;
int b = (int) (Math.random() * 10) + 1;
int ans1 = right(arr, n, a, b);
int ans2 = minTime1(arr, n, a, b);
int ans3 = minTime2(arr, n, a, b);
if (ans1 != ans2 || ans2 != ans3) {
printArray(arr);
System.out.println("n : " + n);
System.out.println("a : " + a);
System.out.println("b : " + b);
System.out.println(ans1 + " , " + ans2 + " , " + ans3);
System.out.println("===============");
break;
}
}
System.out.println("测试结束");
}
习题14 给定一个二维数组matrix，一个人必须从左上角出发，最后到达右下角沿途只可以向下或者向右走，沿途的数字都累加就是距离累加和返回最小距离累加和
public static int minPathSum1(int[][] m) {
if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
return 0;
}
int row = m.length;
int col = m[0].length;
int[][] dp = new int[row][col];
dp[0][0] = m[0][0];
for (int i = 1; i < row; i++) {
dp[i][0] = dp[i - 1][0] + m[i][0];
}
for (int j = 1; j < col; j++) {
dp[0][j] = dp[0][j - 1] + m[0][j];
}
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + m[i][j];
}
}
return dp[row - 1][col - 1];
}
public static int minPathSum2(int[][] m) {
if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
return 0;
}
int row = m.length;
int col = m[0].length;
int[] dp = new int[col];
dp[0] = m[0][0];
for (int j = 1; j < col; j++) {
dp[j] = dp[j - 1] + m[0][j];
}
for (int i = 1; i < row; i++) {
dp[0] += m[i][0];
for (int j = 1; j < col; j++) {
dp[j] = Math.min(dp[j - 1], dp[j]) + m[i][j];
}
}
return dp[col - 1];
}
// for test
public static int[][] generateRandomMatrix(int rowSize, int colSize) {
if (rowSize < 0 || colSize < 0) {
return null;
}
int[][] result = new int[rowSize][colSize];
for (int i = 0; i != result.length; i++) {
for (int j = 0; j != result[0].length; j++) {
result[i][j] = (int) (Math.random() * 100);
}
}
return result;
}
// for test
public static void printMatrix(int[][] matrix) {
for (int i = 0; i != matrix.length; i++) {
for (int j = 0; j != matrix[0].length; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
int rowSize = 10;
int colSize = 10;
int[][] m = generateRandomMatrix(rowSize, colSize);
System.out.println(minPathSum1(m));
System.out.println(minPathSum2(m));
}
习题15 arr是货币数组，其中的值都是正数。再给定一个正数aim。每个值都认为是一张货币，即便是值相同的货币也认为每一张都是不同的，返回组成aim的方法数例如：arr = {1,1,1}，aim = 2第0个和第1个能组成2，第1个和第2个能组成2，第0个和第2个能组成2一共就3种方法，所以返回3
public static int coinWays(int[] arr, int aim) {
return process(arr, 0, aim);
}
// arr[index....] 组成正好rest这么多的钱，有几种方法
public static int process(int[] arr, int index, int rest) {
if (rest < 0) {
return 0;
}
if (index == arr.length) { // 没钱了！
return rest == 0 ? 1 : 0;
} else {
return process(arr, index + 1, rest) + process(arr, index + 1, rest - arr[index]);
}
}
public static int dp(int[] arr, int aim) {
if (aim == 0) {
return 1;
}
int N = arr.length;
int[][] dp = new int[N + 1][aim + 1];
dp[N][0] = 1;
for (int index = N - 1; index >= 0; index--) {
for (int rest = 0; rest <= aim; rest++) {
dp[index][rest] = dp[index + 1][rest] + (rest - arr[index] >= 0 ? dp[index + 1][rest - arr[index]] : 0);
}
}
return dp[0][aim];
}
// 为了测试
public static int[] randomArray(int maxLen, int maxValue) {
int N = (int) (Math.random() * maxLen);
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = (int) (Math.random() * maxValue) + 1;
}
return arr;
}
// 为了测试
public static void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// 为了测试
public static void main(String[] args) {
int maxLen = 20;
int maxValue = 30;
int testTime = 1000000;
System.out.println("测试开始");
for (int i = 0; i < testTime; i++) {
int[] arr = randomArray(maxLen, maxValue);
int aim = (int) (Math.random() * maxValue);
int ans1 = coinWays(arr, aim);
int ans2 = dp(arr, aim);
if (ans1 != ans2) {
System.out.println("Oops!");
printArray(arr);
System.out.println(aim);
System.out.println(ans1);
System.out.println(ans2);
break;
}
}
System.out.println("测试结束");
}
习题16 arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。每个值都认为是一种面值，且认为张数是无限的。返回组成aim的方法数例如：arr = {1,2}，aim = 4方法如下：1+1+1+1、1+1+2、2+2一共就3种方法，所以返回3
public static int coinsWay(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim < 0) {
return 0;
}
return process(arr, 0, aim);
}
// arr[index....] 所有的面值，每一个面值都可以任意选择张数，组成正好rest这么多钱，方法数多少？
public static int process(int[] arr, int index, int rest) {
if (index == arr.length) { // 没钱了
return rest == 0 ? 1 : 0;
}
int ways = 0;
for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
ways += process(arr, index + 1, rest - (zhang * arr[index]));
}
return ways;
}
public static int dp1(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim < 0) {
return 0;
}
int N = arr.length;
int[][] dp = new int[N + 1][aim + 1];
dp[N][0] = 1;
for (int index = N - 1; index >= 0; index--) {
for (int rest = 0; rest <= aim; rest++) {
int ways = 0;
for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
ways += dp[index + 1][rest - (zhang * arr[index])];
}
dp[index][rest] = ways;
}
}
return dp[0][aim];
}
public static int dp2(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim < 0) {
return 0;
}
int N = arr.length;
int[][] dp = new int[N + 1][aim + 1];
dp[N][0] = 1;
for (int index = N - 1; index >= 0; index--) {
for (int rest = 0; rest <= aim; rest++) {
dp[index][rest] = dp[index + 1][rest];
if (rest - arr[index] >= 0) {
dp[index][rest] += dp[index][rest - arr[index]];
}
}
}
return dp[0][aim];
}
// 为了测试
public static int[] randomArray(int maxLen, int maxValue) {
int N = (int) (Math.random() * maxLen);
int[] arr = new int[N];
boolean[] has = new boolean[maxValue + 1];
for (int i = 0; i < N; i++) {
do {
arr[i] = (int) (Math.random() * maxValue) + 1;
} while (has[arr[i]]);
has[arr[i]] = true;
}
return arr;
}
// 为了测试
public static void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// 为了测试
public static void main(String[] args) {
int maxLen = 10;
int maxValue = 30;
int testTime = 1000000;
System.out.println("测试开始");
for (int i = 0; i < testTime; i++) {
int[] arr = randomArray(maxLen, maxValue);
int aim = (int) (Math.random() * maxValue);
int ans1 = coinsWay(arr, aim);
int ans2 = dp1(arr, aim);
int ans3 = dp2(arr, aim);
if (ans1 != ans2 || ans1 != ans3) {
System.out.println("Oops!");
printArray(arr);
System.out.println(aim);
System.out.println(ans1);
System.out.println(ans2);
System.out.println(ans3);
break;
}
}
System.out.println("测试结束");
}
习题17 arr是货币数组，其中的值都是正数。再给定一个正数aim。每个值都认为是一张货币，认为值相同的货币没有任何不同，返回组成aim的方法数例如：arr = {1,2,1,1,2,1,2}，aim = 4方法：1+1+1+1、1+1+2、2+2一共就3种方法，所以返回3
public static class Info {
public int[] coins;
public int[] zhangs;
public Info(int[] c, int[] z) {
coins = c;
zhangs = z;
}
}
public static Info getInfo(int[] arr) {
HashMap<Integer, Integer> counts = new HashMap<>();
for (int value : arr) {
if (!counts.containsKey(value)) {
counts.put(value, 1);
} else {
counts.put(value, counts.get(value) + 1);
}
}
int N = counts.size();
int[] coins = new int[N];
int[] zhangs = new int[N];
int index = 0;
for (Entry<Integer, Integer> entry : counts.entrySet()) {
coins[index] = entry.getKey();
zhangs[index++] = entry.getValue();
}
return new Info(coins, zhangs);
}
public static int coinsWay(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim < 0) {
return 0;
}
Info info = getInfo(arr);
return process(info.coins, info.zhangs, 0, aim);
}
// coins 面值数组，正数且去重
// zhangs 每种面值对应的张数
public static int process(int[] coins, int[] zhangs, int index, int rest) {
if (index == coins.length) {
return rest == 0 ? 1 : 0;
}
int ways = 0;
for (int zhang = 0; zhang * coins[index] <= rest && zhang <= zhangs[index]; zhang++) {
ways += process(coins, zhangs, index + 1, rest - (zhang * coins[index]));
}
return ways;
}
public static int dp1(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim < 0) {
return 0;
}
Info info = getInfo(arr);
int[] coins = info.coins;
int[] zhangs = info.zhangs;
int N = coins.length;
int[][] dp = new int[N + 1][aim + 1];
dp[N][0] = 1;
for (int index = N - 1; index >= 0; index--) {
for (int rest = 0; rest <= aim; rest++) {
int ways = 0;
for (int zhang = 0; zhang * coins[index] <= rest && zhang <= zhangs[index]; zhang++) {
ways += dp[index + 1][rest - (zhang * coins[index])];
}
dp[index][rest] = ways;
}
}
return dp[0][aim];
}
public static int dp2(int[] arr, int aim) {
if (arr == null || arr.length == 0 || aim < 0) {
return 0;
}
Info info = getInfo(arr);
int[] coins = info.coins;
int[] zhangs = info.zhangs;
int N = coins.length;
int[][] dp = new int[N + 1][aim + 1];
dp[N][0] = 1;
for (int index = N - 1; index >= 0; index--) {
for (int rest = 0; rest <= aim; rest++) {
dp[index][rest] = dp[index + 1][rest];
if (rest - coins[index] >= 0) {
dp[index][rest] += dp[index][rest - coins[index]];
}
if (rest - coins[index] * (zhangs[index] + 1) >= 0) {
dp[index][rest] -= dp[index + 1][rest - coins[index] * (zhangs[index] + 1)];
}
}
}
return dp[0][aim];
}
// 为了测试
public static int[] randomArray(int maxLen, int maxValue) {
int N = (int) (Math.random() * maxLen);
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = (int) (Math.random() * maxValue) + 1;
}
return arr;
}
// 为了测试
public static void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// 为了测试
public static void main(String[] args) {
int maxLen = 10;
int maxValue = 20;
int testTime = 1000000;
System.out.println("测试开始");
for (int i = 0; i < testTime; i++) {
int[] arr = randomArray(maxLen, maxValue);
int aim = (int) (Math.random() * maxValue);
int ans1 = coinsWay(arr, aim);
int ans2 = dp1(arr, aim);
int ans3 = dp2(arr, aim);
if (ans1 != ans2 || ans1 != ans3) {
System.out.println("Oops!");
printArray(arr);
System.out.println(aim);
System.out.println(ans1);
System.out.println(ans2);
System.out.println(ans3);
break;
}
}
System.out.println("测试结束");
}
习题18 给定5个参数，N，M，row，col，k表示在NM的区域上，醉汉Bob初始在(row,col)位置Bob一共要迈出k步，且每步都会等概率向上下左右四个方向走一个单位任何时候Bob只要离开NM的区域，就直接死亡返回k步之后，Bob还在N*M的区域的概率
public static double livePosibility1(int row, int col, int k, int N, int M) {
return (double) process(row, col, k, N, M) / Math.pow(4, k);
}
// 目前在row，col位置，还有rest步要走，走完了如果还在棋盘中就获得1个生存点，返回总的生存点数
public static long process(int row, int col, int rest, int N, int M) {
if (row < 0 || row == N || col < 0 || col == M) {
return 0;
}
// 还在棋盘中！
if (rest == 0) {
return 1;
}
// 还在棋盘中！还有步数要走
long up = process(row - 1, col, rest - 1, N, M);
long down = process(row + 1, col, rest - 1, N, M);
long left = process(row, col - 1, rest - 1, N, M);
long right = process(row, col + 1, rest - 1, N, M);
return up + down + left + right;
}
public static double livePosibility2(int row, int col, int k, int N, int M) {
long[][][] dp = new long[N][M][k + 1];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
dp[i][j][0] = 1;
}
}
for (int rest = 1; rest <= k; rest++) {
for (int r = 0; r < N; r++) {
for (int c = 0; c < M; c++) {
dp[r][c][rest] = pick(dp, N, M, r - 1, c, rest - 1);
dp[r][c][rest] += pick(dp, N, M, r + 1, c, rest - 1);
dp[r][c][rest] += pick(dp, N, M, r, c - 1, rest - 1);
dp[r][c][rest] += pick(dp, N, M, r, c + 1, rest - 1);
}
}
}
return (double) dp[row][col][k] / Math.pow(4, k);
}
public static long pick(long[][][] dp, int N, int M, int r, int c, int rest) {
if (r < 0 || r == N || c < 0 || c == M) {
return 0;
}
return dp[r][c][rest];
}
public static void main(String[] args) {
System.out.println(livePosibility1(6, 6, 10, 50, 50));
System.out.println(livePosibility2(6, 6, 10, 50, 50));
}
习题19 给定3个参数，N，M，K怪兽有N滴血，等着英雄来砍自己英雄每一次打击，都会让怪兽流失[0～M]的血量到底流失多少？每一次在[0～M]上等概率的获得一个值求K次打击之后，英雄把怪兽砍死的概率
public static double right(int N, int M, int K) {
if (N < 1 || M < 1 || K < 1) {
return 0;
}
long all = (long) Math.pow(M + 1, K);
long kill = process(K, M, N);
return (double) ((double) kill / (double) all);
}
// 怪兽还剩hp点血
// 每次的伤害在[0~M]范围上
// 还有times次可以砍
// 返回砍死的情况数！
public static long process(int times, int M, int hp) {
if (times == 0) {
return hp <= 0 ? 1 : 0;
}
if (hp <= 0) {
return (long) Math.pow(M + 1, times);
}
long ways = 0;
for (int i = 0; i <= M; i++) {
ways += process(times - 1, M, hp - i);
}
return ways;
}
public static double dp1(int N, int M, int K) {
if (N < 1 || M < 1 || K < 1) {
return 0;
}
long all = (long) Math.pow(M + 1, K);
long[][] dp = new long[K + 1][N + 1];
dp[0][0] = 1;
for (int times = 1; times <= K; times++) {
dp[times][0] = (long) Math.pow(M + 1, times);
for (int hp = 1; hp <= N; hp++) {
long ways = 0;
for (int i = 0; i <= M; i++) {
if (hp - i >= 0) {
ways += dp[times - 1][hp - i];
} else {
ways += (long) Math.pow(M + 1, times - 1);
}
}
dp[times][hp] = ways;
}
}
long kill = dp[K][N];
return (double) ((double) kill / (double) all);
}
public static double dp2(int N, int M, int K) {
if (N < 1 || M < 1 || K < 1) {
return 0;
}
long all = (long) Math.pow(M + 1, K);
long[][] dp = new long[K + 1][N + 1];
dp[0][0] = 1;
for (int times = 1; times <= K; times++) {
dp[times][0] = (long) Math.pow(M + 1, times);
for (int hp = 1; hp <= N; hp++) {
dp[times][hp] = dp[times][hp - 1] + dp[times - 1][hp];
if (hp - 1 - M >= 0) {
dp[times][hp] -= dp[times - 1][hp - 1 - M];
} else {
dp[times][hp] -= Math.pow(M + 1, times - 1);
}
}
}
long kill = dp[K][N];
return (double) ((double) kill / (double) all);
}
public static void main(String[] args) {
int NMax = 10;
int MMax = 10;
int KMax = 10;
int testTime = 200;
System.out.println("测试开始");
for (int i = 0; i < testTime; i++) {
int N = (int) (Math.random() * NMax);
int M = (int) (Math.random() * MMax);
int K = (int) (Math.random() * KMax);
double ans1 = right(N, M, K);
double ans2 = dp1(N, M, K);
double ans3 = dp2(N, M, K);
if (ans1 != ans2 || ans1 != ans3) {
System.out.println("Oops!");
break;
}
}
System.out.println("测试结束");
}
习题20 arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。每个值都认为是一种面值，且认为张数是无限的。返回组成aim的最少货币数
public static int minCoins(int[] arr, int aim) {
return process(arr, 0, aim);
}
// arr[index...]面值，每种面值张数自由选择，
// 搞出rest正好这么多钱，返回最小张数
// 拿Integer.MAX_VALUE标记怎么都搞定不了
public static int process(int[] arr, int index, int rest) {
if (index == arr.length) {
return rest == 0 ? 0 : Integer.MAX_VALUE;
} else {
int ans = Integer.MAX_VALUE;
for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
int next = process(arr, index + 1, rest - zhang * arr[index]);
if (next != Integer.MAX_VALUE) {
ans = Math.min(ans, zhang + next);
}
}
return ans;
}
}
public static int dp1(int[] arr, int aim) {
if (aim == 0) {
return 0;
}
int N = arr.length;
int[][] dp = new int[N + 1][aim + 1];
dp[N][0] = 0;
for (int j = 1; j <= aim; j++) {
dp[N][j] = Integer.MAX_VALUE;
}
for (int index = N - 1; index >= 0; index--) {
for (int rest = 0; rest <= aim; rest++) {
int ans = Integer.MAX_VALUE;
for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
int next = dp[index + 1][rest - zhang * arr[index]];
if (next != Integer.MAX_VALUE) {
ans = Math.min(ans, zhang + next);
}
}
dp[index][rest] = ans;
}
}
return dp[0][aim];
}
public static int dp2(int[] arr, int aim) {
if (aim == 0) {
return 0;
}
int N = arr.length;
int[][] dp = new int[N + 1][aim + 1];
dp[N][0] = 0;
for (int j = 1; j <= aim; j++) {
dp[N][j] = Integer.MAX_VALUE;
}
for (int index = N - 1; index >= 0; index--) {
for (int rest = 0; rest <= aim; rest++) {
dp[index][rest] = dp[index + 1][rest];
if (rest - arr[index] >= 0
&& dp[index][rest - arr[index]] != Integer.MAX_VALUE) {
dp[index][rest] = Math.min(dp[index][rest], dp[index][rest - arr[index]] + 1);
}
}
}
return dp[0][aim];
}
// 为了测试
public static int[] randomArray(int maxLen, int maxValue) {
int N = (int) (Math.random() * maxLen);
int[] arr = new int[N];
boolean[] has = new boolean[maxValue + 1];
for (int i = 0; i < N; i++) {
do {
arr[i] = (int) (Math.random() * maxValue) + 1;
} while (has[arr[i]]);
has[arr[i]] = true;
}
return arr;
}
// 为了测试
public static void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// 为了测试
public static void main(String[] args) {
int maxLen = 20;
int maxValue = 30;
int testTime = 300000;
System.out.println("功能测试开始");
for (int i = 0; i < testTime; i++) {
int N = (int) (Math.random() * maxLen);
int[] arr = randomArray(N, maxValue);
int aim = (int) (Math.random() * maxValue);
int ans1 = minCoins(arr, aim);
int ans2 = dp1(arr, aim);
int ans3 = dp2(arr, aim);
if (ans1 != ans2 || ans1 != ans3) {
System.out.println("Oops!");
printArray(arr);
System.out.println(aim);
System.out.println(ans1);
System.out.println(ans2);
break;
}
}
System.out.println("功能测试结束");
}
习题21 给定一个正数n，求n的裂开方法数，规定：后面的数不能比前面的数小比如4的裂开方法有：1+1+1+1、1+1+2、1+3、2+2、45种，所以返回5
// n为正数
public static int ways(int n) {
if (n < 0) {
return 0;
}
if (n == 1) {
return 1;
}
return process(1, n);
}
// 上一个拆出来的数是pre
// 还剩rest需要去拆
// 返回拆解的方法数
public static int process(int pre, int rest) {
if (rest == 0) {
return 1;
}
if (pre > rest) {
return 0;
}
int ways = 0;
for (int first = pre; first <= rest; first++) {
ways += process(first, rest - first);
}
return ways;
}
public static int dp1(int n) {
if (n < 0) {
return 0;
}
if (n == 1) {
return 1;
}
int[][] dp = new int[n + 1][n + 1];
for (int pre = 1; pre <= n; pre++) {
dp[pre][0] = 1;
dp[pre][pre] = 1;
}
for (int pre = n - 1; pre >= 1; pre--) {
for (int rest = pre + 1; rest <= n; rest++) {
int ways = 0;
for (int first = pre; first <= rest; first++) {
ways += dp[first][rest - first];
}
dp[pre][rest] = ways;
}
}
return dp[1][n];
}
public static int dp2(int n) {
if (n < 0) {
return 0;
}
if (n == 1) {
return 1;
}
int[][] dp = new int[n + 1][n + 1];
for (int pre = 1; pre <= n; pre++) {
dp[pre][0] = 1;
dp[pre][pre] = 1;
}
for (int pre = n - 1; pre >= 1; pre--) {
for (int rest = pre + 1; rest <= n; rest++) {
dp[pre][rest] = dp[pre + 1][rest];
dp[pre][rest] += dp[pre][rest - pre];
}
}
return dp[1][n];
}
public static void main(String[] args) {
int test = 39;
System.out.println(ways(test));
System.out.println(dp1(test));
System.out.println(dp2(test));
}
习题22 给定一个正数数组arr，请把arr中所有的数分成两个集合，尽量让两个集合的累加和接近返回：最接近的情况下，较小集合的累加和
public static int right(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
int sum = 0;
for (int num : arr) {
sum += num;
}
return process(arr, 0, sum / 2);
}
// arr[i...]可以自由选择，请返回累加和尽量接近rest，但不能超过rest的情况下，最接近的累加和是多少？
public static int process(int[] arr, int i, int rest) {
if (i == arr.length) {
return 0;
} else { // 还有数，arr[i]这个数
// 可能性1，不使用arr[i]
int p1 = process(arr, i + 1, rest);
// 可能性2，要使用arr[i]
int p2 = 0;
if (arr[i] <= rest) {
p2 = arr[i] + process(arr, i + 1, rest - arr[i]);
}
return Math.max(p1, p2);
}
}
public static int dp(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
int sum = 0;
for (int num : arr) {
sum += num;
}
sum /= 2;
int N = arr.length;
int[][] dp = new int[N + 1][sum + 1];
for (int i = N - 1; i >= 0; i--) {
for (int rest = 0; rest <= sum; rest++) {
// 可能性1，不使用arr[i]
int p1 = dp[i + 1][rest];
// 可能性2，要使用arr[i]
int p2 = 0;
if (arr[i] <= rest) {
p2 = arr[i] + dp[i + 1][rest - arr[i]];
}
dp[i][rest] = Math.max(p1, p2);
}
}
return dp[0][sum];
}
public static int[] randomArray(int len, int value) {
int[] arr = new int[len];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * value);
}
return arr;
}
public static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
public static void main(String[] args) {
int maxLen = 20;
int maxValue = 50;
int testTime = 10000;
System.out.println("测试开始");
for (int i = 0; i < testTime; i++) {
int len = (int) (Math.random() * maxLen);
int[] arr = randomArray(len, maxValue);
int ans1 = right(arr);
int ans2 = dp(arr);
if (ans1 != ans2) {
printArray(arr);
System.out.println(ans1);
System.out.println(ans2);
System.out.println("Oops!");
break;
}
}
System.out.println("测试结束");
}
习题23 给定一个正数数组arr，请把arr中所有的数分成两个集合如果arr长度为偶数，两个集合包含数的个数要一样多如果arr长度为奇数，两个集合包含数的个数必须只差一个请尽量让两个集合的累加和接近返回：最接近的情况下，较小集合的累加和
public static int right(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
int sum = 0;
for (int num : arr) {
sum += num;
}
if ((arr.length & 1) == 0) {
return process(arr, 0, arr.length / 2, sum / 2);
} else {
return Math.max(process(arr, 0, arr.length / 2, sum / 2), process(arr, 0, arr.length / 2 + 1, sum / 2));
}
}
// arr[i....]自由选择，挑选的个数一定要是picks个，累加和<=rest, 离rest最近的返回
public static int process(int[] arr, int i, int picks, int rest) {
if (i == arr.length) {
return picks == 0 ? 0 : -1;
} else {
int p1 = process(arr, i + 1, picks, rest);
// 就是要使用arr[i]这个数
int p2 = -1;
int next = -1;
if (arr[i] <= rest) {
next = process(arr, i + 1, picks - 1, rest - arr[i]);
}
if (next != -1) {
p2 = arr[i] + next;
}
return Math.max(p1, p2);
}
}
public static int dp(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
int sum = 0;
for (int num : arr) {
sum += num;
}
sum /= 2;
int N = arr.length;
int M = (N + 1) / 2;
int[][][] dp = new int[N + 1][M + 1][sum + 1];
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= M; j++) {
for (int k = 0; k <= sum; k++) {
dp[i][j][k] = -1;
}
}
}
for (int rest = 0; rest <= sum; rest++) {
dp[N][0][rest] = 0;
}
for (int i = N - 1; i >= 0; i--) {
for (int picks = 0; picks <= M; picks++) {
for (int rest = 0; rest <= sum; rest++) {
int p1 = dp[i + 1][picks][rest];
// 就是要使用arr[i]这个数
int p2 = -1;
int next = -1;
if (picks - 1 >= 0 && arr[i] <= rest) {
next = dp[i + 1][picks - 1][rest - arr[i]];
}
if (next != -1) {
p2 = arr[i] + next;
}
dp[i][picks][rest] = Math.max(p1, p2);
}
}
}
if ((arr.length & 1) == 0) {
return dp[0][arr.length / 2][sum];
} else {
return Math.max(dp[0][arr.length / 2][sum], dp[0][(arr.length / 2) + 1][sum]);
}
}
public static int dp2(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
int sum = 0;
for (int num : arr) {
sum += num;
}
sum >>= 1;
int N = arr.length;
int M = (arr.length + 1) >> 1;
int[][][] dp = new int[N][M + 1][sum + 1];
for (int i = 0; i < N; i++) {
for (int j = 0; j <= M; j++) {
for (int k = 0; k <= sum; k++) {
dp[i][j][k] = Integer.MIN_VALUE;
}
}
}
for (int i = 0; i < N; i++) {
for (int k = 0; k <= sum; k++) {
dp[i][0][k] = 0;
}
}
for (int k = 0; k <= sum; k++) {
dp[0][1][k] = arr[0] <= k ? arr[0] : Integer.MIN_VALUE;
}
for (int i = 1; i < N; i++) {
for (int j = 1; j <= Math.min(i + 1, M); j++) {
for (int k = 0; k <= sum; k++) {
dp[i][j][k] = dp[i - 1][j][k];
if (k - arr[i] >= 0) {
dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][j - 1][k - arr[i]] + arr[i]);
}
}
}
}
return Math.max(dp[N - 1][M][sum], dp[N - 1][N - M][sum]);
}
// for test
public static int[] randomArray(int len, int value) {
int[] arr = new int[len];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * value);
}
return arr;
}
// for test
public static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
// for test
public static void main(String[] args) {
int maxLen = 10;
int maxValue = 50;
int testTime = 10000;
System.out.println("测试开始");
for (int i = 0; i < testTime; i++) {
int len = (int) (Math.random() * maxLen);
int[] arr = randomArray(len, maxValue);
int ans1 = right(arr);
int ans2 = dp(arr);
int ans3 = dp2(arr);
if (ans1 != ans2 || ans1 != ans3) {
printArray(arr);
System.out.println(ans1);
System.out.println(ans2);
System.out.println(ans3);
System.out.println("Oops!");
break;
}
}
System.out.println("测试结束");
}
习题24 N皇后问题是指在N*N的棋盘上要摆N个皇后，要求任何两个皇后不同行、不同列， 也不在同一条斜线上给定一个整数n，返回n皇后的摆法有多少种。n=1，返回1n=2或3，2皇后和3皇后问题无论怎么摆都不行，返回0n=8，返回92
public static int num1(int n) {
if (n < 1) {
return 0;
}
int[] record = new int[n];
return process1(0, record, n);
}
// 当前来到i行，一共是0~N-1行
// 在i行上放皇后，所有列都尝试
// 必须要保证跟之前所有的皇后不打架
// int[] record record[x] = y 之前的第x行的皇后，放在了y列上
// 返回：不关心i以上发生了什么，i.... 后续有多少合法的方法数
public static int process1(int i, int[] record, int n) {
if (i == n) {
return 1;
}
int res = 0;
// i行的皇后，放哪一列呢？j列，
for (int j = 0; j < n; j++) {
if (isValid(record, i, j)) {
record[i] = j;
res += process1(i + 1, record, n);
}
}
return res;
}
public static boolean isValid(int[] record, int i, int j) {
// 0..i-1
for (int k = 0; k < i; k++) {
if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {
return false;
}
}
return true;
}
// 请不要超过32皇后问题
public static int num2(int n) {
if (n < 1 || n > 32) {
return 0;
}
// 如果你是13皇后问题，limit 最右13个1，其他都是0
int limit = n == 32 ? -1 : (1 << n) - 1;
return process2(limit, 0, 0, 0);
}
// 7皇后问题
// limit : 0....0 1 1 1 1 1 1 1
// 之前皇后的列影响：colLim
// 之前皇后的左下对角线影响：leftDiaLim
// 之前皇后的右下对角线影响：rightDiaLim
public static int process2(int limit, int colLim, int leftDiaLim, int rightDiaLim) {
if (colLim == limit) {
return 1;
}
// pos中所有是1的位置，是你可以去尝试皇后的位置
int pos = limit & (~(colLim | leftDiaLim | rightDiaLim));
int mostRightOne = 0;
int res = 0;
while (pos != 0) {
mostRightOne = pos & (~pos + 1);
pos = pos - mostRightOne;
res += process2(limit, colLim | mostRightOne, (leftDiaLim | mostRightOne) << 1,
(rightDiaLim | mostRightOne) >>> 1);
}
return res;
}
public static void main(String[] args) {
int n = 15;
long start = System.currentTimeMillis();
System.out.println(num2(n));
long end = System.currentTimeMillis();
System.out.println("cost time: " + (end - start) + "ms");
start = System.currentTimeMillis();
System.out.println(num1(n));
end = System.currentTimeMillis();
System.out.println("cost time: " + (end - start) + "ms");
}
版权声明：本文标题：12.算法习题之暴力递归与动态规划 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/xitong/1725586047a1031191.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论