算法|12.从暴力递归到动态规划5
1.机器人行进问题
题意：假设有排成一行的N个位置记为1~N，N一定大于或等于2
开始时机器人在其中的M位置上(M一定是1~N中的一个)
如果机器人来到1位置，那么下一步只能往右来到2位置；
如果机器人来到N位置，那么下一步只能往左来到N-1位置；
如果机器人来到中间位置，那么下一步可以往左走或者往右走；
规定机器人必须走K步，最终能来到P位置(P也是1~N中的一个)的方法有多少种
给定四个参数 N、M、K、P，返回方法数
解题思路：
- 本题有对应的业务场景，但是我感觉解题其实是从左向右的尝试模型
- 可变参数有两个当前决策的位置以及剩余的步数
- 子过程情况讨论的时候分为3种，开头位置，结束位置及普遍位置；rest=0时分为两种情况要么为0要么为1
核心代码：
递归代码：
public static int ways(int N, int start, int aim, int K) {
if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
return -1;
}
return process(start, K, aim, N);
}
public static int process(int index, int rest, int aim, int N) {
if (rest == 0) {
return index == aim ? 1 : 0;
}
if (index == 1) {
return process(2, rest - 1, aim, N);
}
if (index == N) {
return process(N - 1, rest - 1, aim, N);
}
return process(index - 1, rest - 1, aim, N) + process(index + 1, rest - 1, aim, N);
}
dp代码：
public static int dp(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(ways(5, 2, 4, 6));
System.out.println(dp(5, 2, 4, 6));
}
测试结果：
2.象棋跳马问题
题意：想象一个象棋的棋盘，然后把整个棋盘放入第一象限，棋盘的最左下角是(0,0)位置，那么整个棋盘就是横坐标上9条线、纵坐标上10条线的区域
给你三个 参数 x，y，k
返回“马”从(0,0)位置出发，必须走k步
最后落在(x,y)上的方法数有多少种?
解题思路：
- 本题有对应的业务场景，但是我感觉解题其实是从左向右的尝试模型
- 可变参数有三个，当前决策的位置（横纵）以及剩余的步数
- 子过程情况讨论的时候分为8种，马字；rest=0时分为两种情况要么为0要么为1
核心代码：
递归代码：
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代码：
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 void main(String[] args) {
int x = 7;
int y = 7;
int step = 10;
System.out.println(jump(x, y, step));
System.out.println(dp(x, y, step));
}
测试结果：
3.N皇后问题
题意：N皇后问题是指在N*N的棋盘上要摆N个皇后，
要求任何两个皇后不同行、不同列， 也不在同一条斜线上
给定一个整数n，返回n皇后的摆法有多少种。n=1，返回1
n=2或3，2皇后和3皇后问题无论怎么摆都不行，返回0
n=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;
}
4.喝咖啡（放弃）
题意：给定一个数组arr，arr[i]代表第i号咖啡机泡一杯咖啡的时间
给定一个正数N，表示N个人等着咖啡机泡咖啡，每台咖啡机只能轮流泡咖啡
只有一台咖啡机，一次只能洗一个杯子，时间耗费a，洗完才能洗下一杯
每个咖啡杯也可以自己挥发干净，时间耗费b，咖啡杯可以并行挥发
假设所有人拿到咖啡之后立刻喝干净，
返回从开始等到所有咖啡机变干净的最短时间
三个参数：int[] arr、int N，int a、int b
解题思路：
核心代码：
测试代码：
测试结果：
业务限制尝试模型总结
改写Dp：文章来源：https://www.toymoban.com/news/detail-831020.html
- 分析清楚业务中的参数，确定范围
- 套用其他三种尝试模型
例题总结：文章来源地址https://www.toymoban.com/news/detail-831020.html
- 机器人行进问题——1,7，中间，rest为0，两个可变参数
- 象棋跳马问题——三个可变参数，走马的八种情况；参数的范围和方向
- N皇后问题——目前只掌握题意和递归
- 喝咖啡——放弃…
到了这里，关于算法12.从暴力递归到动态规划5的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
