阿源的知识库动态规划
动态规划_1
简介
初步介绍暴力递归写题， 怎么加缓存表，并改成动态规划版
从左往右尝试模型：
样本对应模型：
范围尝试模型：
1. 机器人走路
题目及思路
假设有排成一行的N个位置，记为1~N， N -定大于或等于2 开始时机器人在其中的M位置上(M一-定是1~N中的一个) 如果机器人来到1位置，那么下一步只能往右来到2位置; 如果机器人来到N位置，那么下一步只能往左来到N-1位置; 如果机器人来到中间位置，那么下一步可以往左走或者往右走; 规定机器人必须走K步，最终能来到P位置(P也是1 ~N中的一-个)的方法有多少种 给定四个参数N、M、K、P，返回方法数。
java
// N矩阵长度 start开始位置 aim目标位置 K步数 返回走到目标的方法数。
// int cur 当前位置, int rest 还有rest步去走, int aim 目标位置, int N 矩阵长度
public static int process1(int cur, int rest, int aim, int N) {
当rest = 0 说明走完了 cur == aim ? 1 : 0
当cur = 1 只能去2位置，rest-1
当cur = 2 只能去n-1位置，rest-1
return (cur+1) + (cur-1) 可以左走和右走
}java
// int cur 当前位置, int rest 还有rest步去走, int aim 目标位置, int N 矩阵长度
// dp[cur][rest] 加入缓存 有重复的状态
// 在process()里 只有cur 和 rest 才会变
public static int process2(int cur, int rest, int aim, int N, int[][] dp) {
如果dp[][] != -1 返回缓存值
当rest = 0 说明走完了 ans = cur == aim ? 1 : 0
当cur = 1 只能去2位置，rest-1 记录ans
当cur = 2 只能去n-1位置，rest-1 记录ans
可以左走和右走 记录ans
dp[][] = ans
return ans;
}
java
// dp最终版
// N矩阵长度 start开始位置 aim目标位置 K步数 返回走到目标的方法数
// 最终要的是dp[start][K]
public static int ways3(int N, int start, int aim, int K) {
列 rest = 1 ; rest <= K
行 cur = 2 ; cur < N
}
dp[cur][rest]
if (rest == 0) return cur == aim ? 1 : 0; 相当于初始化dp表格
第0行不需要 第0列只有aim行是1，其他行是0
int[][] dp = new int[N + 1][K + 1];
dp[aim][0] = 1;
return process1(2, rest - 1, aim, N);
cur = 1 时 ，对于第1行，只依赖左下格dp[2][rest-1]
return process1(N - 1, rest - 1, aim, N);
cur = N 时 ，对于第N行，只依赖左上格dp[n-1][rest-1]
return process1(cur - 1, rest - 1, aim, N) + process1(cur + 1, rest - 1, aim, N);
如果既不是第一行也不是最后一行 ， 依赖 dp[i-1][rest-1]+dp[i+1][rest-1] 左上和左下
由于初始化了第0列 所以一列一列的填就好了（只能一列一列的）代码尝试
java
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);
}dp改造
java
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;
}java
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 0;
}
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];
}2. 纸牌游戏(范围尝试模型)
题目及思路
给定一个整型数组arr,代表数值不同的纸牌排成一条线 玩家A和玩家B依次拿走每张纸牌 规定玩家A先拿，玩家B后拿 但是每个玩家每次只能拿走最左或最右的纸牌 玩家A和玩家B都绝项聪明 请返回最后获胜者的分数
如果A先手 那么自己（A）拿的时候尽可能的大 且 后手拿的尽可能的小
对于B来说 希望先手的人拿的尽可能小 且 自己(B)后手拿的尽可能大java
对于[0-7]位置,存在重复的过程，但是两张表相互依赖
f[0,7]
g[1,7] g[0,6]
f[1,6]f[2,7] f[0,5]f[1,6]
java
// dp分析依赖关系
int N = arr.length;
int[][] fmap = new int[N][N];
int[][] gmap = new int[N][N];
fmap[L][R] gmap[L][R]
第一步 初始化 对于先手来说 L==R 时 一定能拿到最后一个
后手的 gmap[i][i] = 0;
for (int i = 0; i < N; i++) {
fmap[i][i] = arr[i];
}
对于依赖关系来说 只会用到表格的上三角形
对于f来说，依赖的是g表，本位置的下格和左格
int p1 = arr[L] + g2(arr, L + 1, R, fmap, gmap);
int p2 = arr[R] + g2(arr, L, R - 1, fmap, gmap);
对于g来说，依赖的是f表，本位置的下格和左格
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);
由于初始化了f表和g表的主对角线，应该按照对角线进行填充
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++;
}
}
最后需要的是 fmap[0][N - 1], gmap[0][N - 1] max代码尝试
java
// 根据规则，返回获胜者的分数
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) { // 后手获得的0
return 0;
}
int p1 = f1(arr, L + 1, R); // 对手拿走了L位置的数
int p2 = f1(arr, L, R - 1); // 对手拿走了R位置的数
return Math.min(p1, p2);
}dp改造
java
// 加缓存
public static int win2(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int N = arr.length;//（o - n-1够了）
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;
}java
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]);
}动态规划_2
简介
1. 背包问题（从左往右尝试模型）
题目及思路
java
// 所有的货，重量和价值，都在w和v数组里
// 为了方便，其中没有负数
// bag背包容量，不能超过这个载重
// 返回：不超重的情况下，能够得到的最大价值java
// int[] w 重量, int[] v 价值, int index 价值数组长度, int rest 总重量)
public static int process(int[] w, int[] v, int index, int rest) {
总重量 < 0时 可能会有无效解 返回-1
背包长度 = w.length 全部遍历完了返回0
// 要当前货
// 不要当前货 注意判断process()是不是无效解
return max(要当前货 ， 不要当前货)
}java
在上述尝试中 ， 只有index和rest会变
public static int dp(int[] w, int[] v, int bag) {
//只需要 表的长度 和 重量大小
int[][] dp = new int[N + 1][bag + 1];
//初始化
index == w.length 最后一行全是0
//依赖
process(w, v, index + 1, rest); 下一行 当前列
process(w, v, index + 1, rest - w[index]); 下一行 之前列 之间的最大值
由于只依赖下一行，所以应该从倒数第二行开始往上，从左往右和从右往左都可以
}
最后需要的是dp[0][bag]代码尝试
java
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);
}java
// 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);
}dp改造
java
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];
}2. 转化数字为字符
题目及思路
java
规定1和A对应、2和B对应、3和C对应..6和对应
那么一个数字字符串比如"111"就可以转化为:
"AAA"、 "KA"和"AK"
给定一个只有数字字符组成的字符串str,返回有多少种转化结果java
//char[] str , int i 当前位置
public static int process(char[] str, int i) {
i = str.length 有一种方法 [i - 末尾]转化有多少种方法
不能单独面对0字符，因为只有10和20，必须要凑对 所以之前决策错误 返回0总方法
// 可能性1 单个数字转为一个字符
int ways = process(str, i + 1);
// 可能性2 两个数字转为一个字符 要保证<length 和 < 27
ways += process(str, i + 2);
}java
一个可变参数
int[] dp = new int[N + 1];
初始化 i == str.length dp[N] = 1
只依赖后面的位置 从右往左填
只有当str[i]!='0'的时候，才有方法
需要dp[0]代码尝试
java
// 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改造
java
// 从右往左的动态规划
// 就是上面方法的动态规划版本
// 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];
}3. 剪贴纸
题目及思路
java
给定一个字符串str,给定一个字符串类型的数组arr,出现的字符都是小写英文
arr每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来
返回需要至少多少张贴纸可以完成这个任务。
例子: str= "babac", arr = {"a","c","abcd"}
至少需要两张贴纸"ba"和"abcd"，因为使用这两张贴纸，把每一个字符单独剪开，含
有2个a、2个b、1个c。是可以拼出str的。所以返回3。
// 本题测试链接：https://leetcode.com/problems/stickers-to-spell-word代码尝试
java
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();
}4. 最长公共子序列（样本对应模型）
题目及思路
java
str1 str2 子序列是可以跳的java
// str1[0...i]和str2[0...j]，这个范围上最长公共子序列长度是多少？代码尝试
java
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);
}java
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));
}
}dp改写
java
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];
// i == 0 && j == 0
dp[0][0] = str1[0] == str2[0] ? 1 : 0;
// i == 0 str1[i] == str2[j] return 1 要不然依赖 j-1
for (int j = 1; j < M; j++) {
dp[0][j] = str1[0] == str2[j] ? 1 : dp[0][j - 1];
}
// j == 0 str1[i] == str2[j] return 1 要不然依赖 i-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];
}动态规划_3
1.最长回文子序列
题目及思路
java
给定一个字符串str,返回这个字符串的最长回文子序列长度
比如: str= “a12b3c43def2ghi1kpm"
最长回文子序列是"1234321" 或者"123c321"
返回长度7
// 测试链接：https://leetcode.com/problems/longest-palindromic-subsequence/java
利用最长公共子序列
str 和 str逆序 求两个的最长公共子序列java
// str[L..R]最长回文子序列长度返回
public static int f(char[] str, int L, int R) {
L == R 只有一个字符 肯定是回文
L == R - 1 两个字符 相等就是回文2
int p1 = f(str, L + 1, R - 1); // 不以L和R
int p2 = f(str, L, R - 1); // 以L开头 不以R结尾
int p3 = f(str, L + 1, R); // 以R开头 不以L结尾
int p4 = str[L] != str[R] ? 0 : (2 + f(str, L + 1, R - 1)); // 以L和R开头结尾，长度+2
}代码尝试
java
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));
}dp改写
java
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];
}2. 象棋跳马(三维动态规划)
题目及思路
java
请同学们自行搜索或者想象一个象棋的棋盘,
然后把整个棋盘放入第一象限，棋盘的最左下角是(0,0)位置
那么整个棋盘就是横坐标上9条线、纵坐标上10条线的区域
给你三个参数x, y, k
返回“马” 从(0,0)位置出发，必须走k步
最后落在(x,y)_上的方法数有多少种?java
// int x, int y 当前位置, int rest还剩多少步, int a, int b 目标位置
public static int process(int x, int y, int rest, int a, int b) {
}代码尝试
java
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;
}dp改造
java
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];
}3. 喝咖啡(模拟排队+dp)
题目及思路
java
// 数组arr代表每一个咖啡机冲一杯咖啡的时间，每个咖啡机只能串行的制造咖啡。
// 现在有n个人需要喝咖啡，只能用咖啡机来制造咖啡。
// 认为每个人喝咖啡的时间非常短，冲好的时间即是喝完的时间。
// 每个人喝完之后咖啡杯可以选择洗或者自然挥发干净，只有一台洗咖啡杯的机器，只能串行的洗咖啡杯。
// 洗杯子的机器洗完一个杯子时间为a，任何一个杯子自然挥发干净的时间为b。
// 四个参数：arr, n, a, b
// 假设时间点从0开始，返回所有人喝完咖啡并洗完咖啡杯的全部过程结束后，至少来到什么时间点。[1 , 3 ,7] 咖啡机泡一杯咖啡要多少时间 ）
需要用小根堆来模拟排队 按照（a,b） a+b来进行排序
(0,1) 0号时间点需要泡咖啡1分钟 完成之后(1 ，1）
(0,3)
(0,7)
模拟排队 得到每个人多久可以开始洗杯子 相当于得到最优的排队方式
然后利用动态规划 选择洗杯子还是挥发代码尝试
java
// 以下为贪心+优良暴力
public static class Machine {
public int timePoint; // 当前时间点
public int workTime; // 咖啡机i号的泡好一杯的时间
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;
//第i个人在哪个时刻喝完的咖啡
drinks[i] = cur.timePoint;
heap.add(cur);
}
return bestTime(drinks, a, b, 0, 0);
}
// drinks 所有杯子可以开始洗的时间
// wash 单杯洗干净的时间（串行）
// air 挥发干净的时间(并行)
// index 当前需要选择的人index
// free 洗的机器什么时间点可用
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);
}dp改造(业务限制模型)
java
// 贪心+优良尝试改成动态规划
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];
}动态规划_4
简介
为什么要建立空间感？
数组压缩技巧：依赖左边和上边 依赖左上角和上面
依赖左边，左上角和上面（需要一个临时变量记录左上角的值）
1. 二维dp优化一维dp
题目及思路
java
java
由于dp数组 初始化了第0行和第0列
而且格子只依赖自己的左边和上边
因此只需要从 1 - n-1列 一行一行的填充
把原来需要二维的dp变为一维的dp
dp代码
java
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];
}优化(空间压缩技巧)
java
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];
}2.从左往右的模型
题目及思路
arr是货币数组，其中的值都是正数。再给定一一个正数aim。
每个值都认为是一张货币，
即便是值相同的货币也认为每一张都是不同的，
,返回组成aim的方法数
例如: arr= {1,1,1}，aim= 2
第0个和第1个能组成2，第1个和第2个能组 成2，第0个和第2个能组成2
一共就3种方法，所以返回3java
从左往右的模型dp代码
java
// 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];
}3. 有枚举类型的dp优化
题目及思路
java
arr是面值数组，其中的值都是正数且没有重复。再给定一-个正数aim。
每个值都认为是一种面值，且认为张数是无限的。
返回组成aim的方法数
例如: arr= {1,2}，aim=4
方法如下: 1+1+1+1、1+1+2、 2+2
一共就3种方法，所以返回3java
// 特殊需要优化 每一格竟然需要一个循环才能出答案
// 枚举行为
for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
ways += process(arr, index + 1, rest - (zhang * arr[index]));
}
[index][rest]为当前位置
[index+1][rest]为下面
[index][rest] = [index+1][rest]+[index+1][rest-1*arr[index]]+[index+1][rest - 2*arr[index]]
[index][rest - arr[index]] = [index+1][rest-1*arr[index]]+[index+1][rest - 2*arr[index]]
因此 [index][rest] = [index+1][rest] + [index][rest - arr[index]]代码尝试
java
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;
}dp优化
java
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];
}4. 枚举类型难度max
题目及思路
java
arr是货币数组，其中的值都是正数。再给定一个正数aim。
每个值都认为是一张货币，
认为值相同的货币没有任何不同，
返回组成aim的方法数
例如: arr= {1,2,1,1,2,1.2}， aim=4
方法: 1+1+1+1、1+1+2. 2+2
一共就3种方法，所以返回3代码尝试
java
public static class Info {
public int[] coins;
public int[] zhangs;
public Info(int[] c, int[] z) {
coins = c;
zhangs = z;
}
}
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;
}dp改造
java
ublic 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];
}动态规划_5
1. 砍怪兽
题目及思路
java
给定3个参数，N, M, K
怪兽有N滴血，等着英雄来砍自己
英雄每一次打击， 都会让怪兽流失[0~M]的血量
到底流失多少?每一次在[0~M]上等概率的获得- -个值
求K次打击之后，英雄把怪兽砍死的概率代码尝试
java
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;
}dp改造
java
// int N 血量hp, in t M, int K 次数time
public static double dp1(int N, in t 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++) {
// 怪兽已经死了 [0 1 2 3] 还有两刀 （4^2）
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);
}斜率优化的dp
java
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);
}2. 选纸币
题目及思路
java
arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。
每个值都认为是一种面值，且认为张数是无限的。
返回组成aim的最少货币数代码尝试
java
// 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];
}斜率优化dp
java
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];
}3. 拆数字
题目及思路
java
把一个数字拆成几个java
// 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];
}dp优化
java
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];
}动态规划_6
简介
一定要逼自己找到不违反原则情况下的暴力尝试! 如果你找到的暴力尝试，不符合原则，马上舍弃!找新的! 如果某个题目突破了设计原则，-定极难极难，面试中出现概率低于5% !
1)从左往右的尝试模型 2)范围上的尝试模型 3)多样本位置全对应的尝试模型 4)寻找业务限制的尝试模型
1.选数累加和最接近一个数
题目及思路
java
给定一个正数数组arr,
请把arr中所有的数分成两个集合，尽量让两个集合的累加和接近
返回:最接近的情况下，较小集合的累加和代码尝试
java
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);
}cc
// 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);
}
}dp改造
java
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];
}2. 第一题升级版
题目及思路
java
给定一个正数数组arr,请把arr中所有的数分成两个集合
如果arr长度为偶数，
两个集合包含数的个数要一样多
如果arr长度为奇数,
两个集合包含数的个数必须只差一个
请尽量让两个集合的累加和接近
返回:
最接近的情况下，较小集合的累加和代码尝试
java
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);
}
}dp改写
java
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]);
}
}3. N皇后
题目及解法
java
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;
}java
// 请不要超过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;
}