讲述暴力递归和动态规划的关系 =》去重的过程
记忆化搜索 傻缓存
动态规划都可以由暴力递归改进过来，解决动态规划的套路
常见的尝试模型
设计尝试过程的原则
本节是暴力递归到动态规划的总纲（很重要）
后续的课都是在讲述这一系列的套路
1、尝试=》 分辨出来所有的参数，找到所有的可变参数以及固定的值（边界）
2、可变参数的组合是什么，表大小根据可变参数的变化范围来确定
3、已知固定位置的依赖，有具体参数的例子（范围的两端）
4、知道在表中的最终想要的位置，baseCase固定的行列（确定好baseCase）
5、分析任意位置的依赖
假设有排成一行的N个位置记为1~N，N一定大于或等于2
开始时机器人在其中的M位置上(M一定是1~N中的一个)
如果机器人来到1位置，那么下一步只能往右来到2位置；
如果机器人来到N位置，那么下一步只能往左来到N-1位置；
如果机器人来到中间位置，那么下一步可以往左走或者往右走；
规定机器人必须走K步，最终能来到P位置(P也是1~N中的一个)的方法有多少种
给定四个参数 N、M、K、P，返回方法数
使用HashMap来存储当前的状态
public static void main(String[] args) {
System.out.println(ways1(5, 2, 4, 6));
}
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;
}
HashMap<String, Integer> cache = new HashMap<>();
return process(start, K, aim, N, cache);
}
// 机器人还有rest步需要去走，
// 最终的目标是aim，
// 有哪些位置？1~N
public static int process(int cur, int res, int aim, int N, HashMap<String, Integer> cache) {
String key = String.valueOf(cur) + "_" + String.valueOf(res);
if (cache.containsKey(key)) {
return cache.get(key);
}
// baseCase
int ans = 0;
if (res == 0) {
ans = cur == aim ? 1 : 0;
cache.put(key, ans);
return ans;
}
// 边界情况
if (cur == 1) {
ans = process(cur + 1, res - 1, aim, N, cache);
cache.put(key, ans);
return ans;
}
if (cur == N) {
ans = process(cur - 1, res - 1, aim, N, cache);
cache.put(key, ans);
return ans;
}
// 任意情况
ans = process(cur - 1, res - 1, aim, N, cache)
+ process(cur + 1, res - 1, aim, N, cache);
cache.put(key, ans);
return ans;
}
修改cache为指定大小的数组，空间复杂度降下来了
// 机器人还有rest步需要去走，
// 最终的目标是aim，
// 有哪些位置？1~N
public static int process(int cur, int res, int aim, int N, int[][] cache) {
if (cache[cur][res] != 0 ) {
return cache[cur][res];
}
// baseCase
int ans = 0;
if (res == 0) {
ans = cur == aim ? 1 : 0;
cache[cur][res] = ans;
return ans;
}
// 边界情况
if (cur == 1) {
ans = process(cur + 1, res - 1, aim, N, cache);
cache[cur][res] = ans;
return ans;
}
if (cur == N) {
ans = process(cur - 1, res - 1, aim, N, cache);
cache[cur][res] = ans;
return ans;
}
// 任意情况
ans = process(cur - 1, res - 1, aim, N, cache)
+ process(cur + 1, res - 1, aim, N, cache);
cache[cur][res] = ans;
return ans;
}
public class Test {
public static void main(String[] args) {
System.out.println(ways1(5, 2, 4, 6));
}
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;
}
int[][] dp = new int[N + 2][K + 1];
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= K; j++) {
dp[i][j] = -1;
}
}
return process(start, K, aim, N, dp);
}
// 机器人还有rest步需要去走，
// 最终的目标是aim，
// 有哪些位置？1~N
public static int process(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 = process(2, rest - 1, aim, N, dp);
} else if (cur == N) {
ans = process(N - 1, rest - 1, aim, N, dp);
} else {
ans = process(cur - 1, rest - 1, aim, N, dp)
+ process(cur + 1, rest - 1, aim, N, dp);
}
dp[cur][rest] = ans;
return ans;
}
}
画出table表：
动态规划是直接把暴力递归的思路直接架空，拿出所对应的确定的值进行计算
public class Test {
public static void main(String[] args) {
// K:剩余步数
System.out.println(process(2, 4, 6, 5));
}
// 机器人还有rest步需要去走，
// 最终的目标是aim，
// 有哪些位置？1~N
public static int process(int start, int aim, int K, int N) {
if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
return -1;
}
int[][] dp = new int[N + 1][K + 1];
// cur已经到aim，而剩余步数也为0了
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];
}
}
给定一个整型数组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 class JumpHorse{
public static void main(String[] args) {
int enda = 5;
int endb = 7;
int rest = 10;
System.out.println(process(0, 0, enda, endb, rest));
}
public static int process(int x, int y, int enda, int endb, int rest) {
if (x < 0 || x > 9 || y < 0 || y > 8) {
return 0;
}
if (rest == 0) {
return x == enda && y == endb ? 1 : 0;
}
int res = 0;
res = process(x+2, y+1, enda, endb, rest-1) +
process(x+1, y+2, enda, endb, rest-1) +
process(x-1, y-2, enda, endb, rest-1) +
process(x-2, y-1, enda, endb, rest-1) +
process(x-1, y+2, enda, endb, rest-1) +
process(x+1, y-2, enda, endb, rest-1) +
process(x+2, y-1, enda, endb, rest-1) +
process(x-2, y+1, enda, endb, rest-1);
return res;
}
}
public class JumpHorse{
public static void main(String[] args) {
int enda = 5;
int endb = 7;
int rest = 10;
System.out.println(waysdp(enda, endb, rest));
}
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];
}
}
暴力递归到动态规划题目。
涉及到一些套路，dp的分析……
public class Test {
public static void main(String[] args) {
processOpen();
}
public static void processOpen() {
int[] arr = new int[]{5, 2, 3};
int aim = 10;
System.out.println(process(arr, 0, aim));
}
public static int process(int[] arr, int idx, int rest) {
if (idx >= arr.length) {
return rest == 0 ? 1 : 0;
}
int sum = 0;
for (int n = 0; n * arr[idx] <= rest; n++) {
sum += process(arr, idx + 1, rest - n * arr[idx]);
}
return sum;
}
}
又叫做顺序依赖，DP过程
public class xx {
public static int process(int[] arr, int idx, int aim) {
int[][] dp = new int[arr.length + 1][aim+1];
dp[arr.length][0] = 1;
for (int i = arr.length-1; i >= 0; i--) {
for (int j = 0; j <= aim; j++) {
dp[i][j] = dp[i + 1][j];
if (j - arr[i] >= 0) {
dp[i][j] += dp[i][j - arr[i]];
}
}
}
return dp[0][aim];
}
}
如果没有枚举过程，那么就没有必要进行dp操作，如果有枚举过程，那么可以对它做优化，《斜率优化》，可以省去重复的操作时间。
空间压缩：
使用一维的数据来代替二维的数据
依赖多个数据的时候，使用两个数组交替着滚动，交替使用（省空间）
1）l-》r（背包问题）
2）范围尝试：L-R（回文）
3）2样本
尝试原则：
1）设计尽量简单，限制可变参数为整数类型，否则可能性太大了
2）可变参数个数尽量少，