从 暴力递归 到 动态规划
动态规划就是暴力尝试减少重复计算的技巧整，而已
这种技巧就是一个大型套路
先写出用尝试的思路解决问题的递归函数，而不用操心时间复杂度
这个过程是无可替代的，没有套路的，只能依靠个人智慧，或者足够多的经验
但是怎么把尝试的版本，优化成动态规划，是有固定套路的，大体步骤如下：
- 找到什么可变参数可以代表一个递归状态，也就是哪些参数一旦确定，返回值就确定了
- 把可变参数的所有组合映射成一张表，有 1 个可变参数就是一维表，2个可变参数就是二维表，……
- 最终答案要的是表中的哪个位置，在表中标出
- 根据递归过程的 basecase，把这张表的最简单、不需要依赖其他位置的那些位置填好值
- 根据递归过程非 basecase 的部分，也就是分析表中的普遍位置需要怎么计算得到，那么这张表的填写顺序也就确定了
- 填好表，返回最终答案在表中位置的值
机器人达到指定位置方法数
【题目】
假设有排成一行的 N 个位置，记为 1~N，N 一定大于或等于 2。开始时机器人在其中的 M 位置上（W 一定是 1~N 中的一个），机器人可以往左走或者往右走，如果机器人来到1位置，那么下一步只能往右来到 2 位置；如果机器人来到 N 位置，那么下一步只能往左来到 N-1 位置。规定机器人必须走 K 步，最终能来到 P 位置（P 也一定是 1~N 中的一个）的方法有多少种。给定四个参数 N、M、K、P，返回方法数。
【例一】
N=5，M=2，K=3，P=3
上面的参数代表所有位置为 1 2 3 4 5。机器人最开始在 2 位置上，必须经过3步，最后到达 3 位置。走的方法只有如下3种：
- 从 2 到 1，从 1 到 2，从 2 到 3
- 从 2 到 3，从 3 到 2，从 2 到 3
- 从 2 到 3，从 3 到 4，从 4 到 3
所以返回方法数3。
【例二】
N=3，M=1，K=3，P=3
上面的参数代表所有位置为 1 2 3。机器人最开始在 1 位置上，必须经过3步，最后到达 3 位置。怎么走也不可能，所以返回方法数 0。
递归版本
public class RobotWalk {static int N = 0;static int M = 0;static int K = 0;static int P = 0;static int robotWalk(int N, int M, int K, int P) {RobotWalk.N = N;RobotWalk.M = M;RobotWalk.K = K;RobotWalk.P = P;return process(M, 0);}static int process(int curM, int curK) {if (curK == K) {return curM == P ? 1 : 0;}int num = 0;if (curM - 1 >= 0) {num += process(curM - 1, curK + 1);}if (curM + 1 <= N) {num += process(curM + 1, curK + 1);}return num;}public static void main(String[] args) {System.out.println(robotWalk(5, 2, 3, 3));System.out.println(robotWalk(3, 1, 3, 3));}}
结果：
3
0
第一版修改
加缓存数组：将每次得到的结果都保存到数组中，如果已经计算过该情况的数据，就直接返回。
代码如下：
public class RobotWalk1 {
static int N = 0;
static int M = 0;
static int K = 0;
static int P = 0;
static int robotWalk(int N, int M, int K, int P) {
RobotWalk1.N = N;
RobotWalk1.M = M;
RobotWalk1.K = K;
RobotWalk1.P = P;
// 这里的容量最大就是 N * K，机器人最多走 K 步，范围在 N
int[][] dp = new int[N + 1][K + 1];
for (int i = 0; i < dp.length; i++) {
for (int j = 0; j < dp[i].length; j++) {
dp[i][j] = -1;
}
}
return process(M, 0, dp);
}
static int process(int curM, int curK, int[][] dp) {
if (curK == K) {
dp[curM][curK] = curM == P ? 1 : 0;
return dp[curM][curK];
}
// 缓存数组没有命中
int num = 0;
if (curM - 1 > 0) {
num += process(curM - 1, curK + 1, dp);
dp[curM][curK] = num;
}
if (curM + 1 <= N) {
num += process(curM + 1, curK + 1, dp);
dp[curM][curK] = num;
}
return dp[curM][curK];
}
}
第二版修改
在第一版修改中使用缓存数组来减少计算，使得空间复杂度从递归版本的 
变成了 
。如果需要进一步优化，那就不能只时将每一步的结果保存到缓存数组中了，就必须要对数组中保存的数据进行进一步的思考。如下图就是缓存数组 dp[N+1][K+1]：
K + 1 行 N + 1 列，初始在 M 点，需要走 K 步到 P 点。其中 N=5，M=2，K=3，P=3。
这个二维数组中有哪些情况是直接可以得到答案的呢？
由代码的 base case 可知：K = 3 时，所有已经走完了 3 步，所以只有 dp[3列][3行] = 1 其他的都是 dp[i列][3行] = 0，如下图：
代码逻辑可知：0 位置不存在，所以机器人一定不能走到 0 ，dp[0列][j行] 都不会使用到 即 dp[0列][j行] = 0
接着看代码
int num = 0;
if (curM - 1 > 0) {
num += process(curM - 1, curK + 1, dp);
dp[curM][curK] = num;
}
if (curM + 1 <= N) {
num += process(curM + 1, curK + 1, dp);
dp[curM][curK] = num;
}
代码可以转为
int num = 0;
if (curM == 1) {
num += process(curM + 1, curK + 1, dp);
dp[curM][curK] = num;
} else if (curM == N) {
num += process(curM - 1, curK + 1, dp);
dp[curM][curK] = num;
} else {
num = process(curM - 1, curK + 1, dp) + process(curM + 1, curK + 1, dp);
dp[curM][curK] = num;
}
逻辑可分解如下
if (走到 1 列) {
向 右下角 [curM + 1, curK + 1] 要结果
} else if (走到 N 位置) {
向 左下角 [curM - 1, curK + 1] 要结果
} else {
向 左下角 + 右下角 要结果
}
最后在数组中填充结果为
可以看到在 M 点的值为 3。
代码实现为：
static int robotWalk(int N, int M, int K, int P) {
if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
return 0;
}
int[][] dp = new int[N + 1][K + 1];
dp[P][K] = 1;
for (int j = K - 1; j >= 0; j--) {
for (int i = N; i > 0; i--) {
if (i == N) {
// 左下角
dp[N][j] = dp[N - 1][j + 1];
} else {
// 左下角 + 右下角
dp[i][j] = dp[i - 1][j + 1] + dp[i + 1][j + 1];
}
}
}
return dp[M][0];
}
当然，还是可以继续优化的，如：每层数组的数都只用一次，那么完全可以用一个以为数组来代替计算：
static int robotWalk(int N, int M, int K, int P) {
if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
return 0;
}
int[] dp = new int[N + 1];
dp[P] = 1;
for (int k = 0; k < K; k++) {
int leftDown = 0;
for (int i = 1; i <= N; i++) {
int temp = dp[i];
if (i == N) {
// 左下角
dp[N] = dp[N - 1];
} else {
// 左下角 + 右下角
dp[i] = leftDown + dp[i + 1];
}
leftDown = temp;
}
}
return dp[M];
}
换钱的最少货币数
给定数组 arr，arr 中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数 aim，代表要找的钱数，求组成 aim 的最少货币
【举例】
arr=[5, 2, 3]，aim=20
4 张 5 元可以组成 20 元，其他的找钱方案都要使用更多张的货币。所以返回 4
arr=[5, 2, 3]，aim=0
不用任何货币就可以组成 0 元，返回 0
arr=[3, 5]，aim=2
根本无法组成 2 元，钱不能找开的情况下默认返回 -1
递归版本
import java.util.Arrays;
public class CoinsMin {
static int getCoinsMin(int[] arr, int aim) {
if (aim == 0) return 0;
if (arr == null || arr.length == 0 || !Arrays.stream(arr).anyMatch(coin -> coin < aim)) return -1;
return process(arr, 0, aim);
}
static int process(int[] arr, int i, int aim) {
if (i == arr.length) return aim == 0 ? 0 : -1;
int minNum = -1;
// 第 i 个硬币使用了 k 个
for (int k = 0; k * arr[i] <= aim; k++) {
int data = process(arr, i + 1, aim - k * arr[i]);
if (data == -1) continue;
minNum = minNum == -1 ? data + k : Math.min(data + k, minNum);
}
return minNum;
}
public static void main(String[] args) {
System.out.println(getCoinsMin(new int[]{5, 2, 3}, 20));
System.out.println(getCoinsMin(new int[]{5, 2, 3}, 0));
System.out.println(getCoinsMin(new int[]{5, 3}, 2));
System.out.println(getCoinsMin(new int[]{5, 2, 3}, 11));
}
}
结果
4
0
-1
3
第一版修改
加数组缓存
fuck~~~，这题不看了，看了好久都没弄出来
动态规划
具体思路请参考 https://blog.csdn.net/sjq_915/article/details/108910004
import java.util.Arrays;
public class CoinsMin2 {
static int getCoinsMin(int[] arr, int aim) {
if (aim == 0) return 0;
if (arr == null || arr.length == 0 || !Arrays.stream(arr).anyMatch(coin -> coin < aim)) return -1;
int[][] dp = new int[arr.length][aim + 1];
for (int i = 0; i < dp.length; i++) {
// 当前的硬币面值
int curCoin = arr[i];
int[] numArr = dp[i];
for (int j = 1; j < numArr.length; j++) {
if (i == 0) {
// 第一行要计算出 j 能被兑换的数量
numArr[j] = j % curCoin == 0 ? j / curCoin : Integer.MAX_VALUE;
} else {
// 上一行的值
int preNum = dp[i - 1][j];
/**
* 当前数 j 能不能被 curCoin 面值 兑换：
* 如果能被兑换那么 dp[i][j] - curCoin = dp[i][j-curCoin] 也能被兑换
* 即：能被 dp[i][j] = dp[i][j-curCoin] + 1 个硬币兑换
*
* 如果上一行（dp[i][j]）有数说明有另一种兑换方法，取小值即可
*/
int preIndex = j - curCoin;
if (preIndex >= 0 && dp[i][preIndex] != Integer.MAX_VALUE) {
dp[i][j] = Math.min(dp[i][preIndex] + 1, preNum);
} else {
dp[i][j] = preNum;
}
}
}
}
return dp[arr.length - 1][aim];
}
}
纸牌博弈
给定一个整型数组 arr，代表数值不同的纸牌排成一条线。玩家 A 和玩家 B 依次拿走每张纸牌，规定玩家 A 先拿，玩家B后拿,但是每个玩家每次只能拿走最左或最右的纸牌，玩家 A 和玩家 B 都绝顶聪明。请返回最后获胜者的分数。
【举例】
arr=[1, 2, 100, 4]
开始时，玩家 A 只能拿走 1 或 4。
如果玩家 A 拿走1，则排列变为 [2,100.4]，接下来玩家 B 可以拿走 2 或 4，然后继续轮到玩家A。
如果开始时玩家 A 拿走 4，则排列变为 [1,2,100]，接下来玩家 B 可以拿走 1 或 100，然后继续轮到玩家 A。
玩家 A 作为绝顶聪明的人不会先拿 4，因为拿 4 之后，玩家 B 将拿走 100。所以玩家 A 会先拿1，让排列变为 [2,100,4]，接下来玩家 6 不管怎么选，100 都会被玩家 A 拿走。玩家 A 会获胜，分数为101。所以返回101。
arr=[1, 100, 2]
开始时，玩家 A 不管拿 1 还是 2，玩家 B 作为绝顶聪明的人，都会把100拿走。玩家 B 会获胜，分数为 100。所以返回 100。
该题的递归解法已经在之前 暴力递归 - 拿纸牌 中完成
直接看代码逻辑来改动态规划：
不论是先手函数还是后手函数，可变参数都是 两个边界 left、right，范围都在 [0, arr.length-1] 上，所以二维数组应该是个正方形
而主函数需要的是 Math.max(first(arr, 0, arr.length - 1), second(arr, 0, arr.length - 1))，也就是需要两个数组中的 [0, arr.length-1] 上的值，即下图中绿色位置上的值
而在数组范围内有个共同的特点：左下边界是无效的，因为 left <= right 不存在类似 [3, 0] 的范围
在 first 函数中，这里假定 arr = [19, 92, 12, 17, 56]
if (left == right) return arr[left];
在 second 函数中
if (left == right) return 0;
first 函数需要 两个值来判断获取到 second(arr, left + 1, right) 和 second(arr, left, right - 1) ，也就是左边数组的 [i][j] 位置依赖右边数组 [i+1][j] 和 [i][j-1] 的值，[i][j] = Math.max(arr[i] + secondArr[i + 1, j], arr[j] + secondArr[i, j - 1])
second 函数需要 两个值来判断获取到 first(arr, left + 1, right) 和 first(arr, left, right - 1) ，也就是右边数组的 [i][j] 位置依赖左边数组 [i+1][j] 和 [i][j-1] 的值，[i][j] = Math.min(firstArr[i + 1, j], firstArr[i, j - 1])
填写完成后：
结果为 109。
代码实现：
public class CardsInLine1 {
static int cardsInLine(int[] arr) {
if (arr == null || arr.length == 0) return 0;
int[][] fArr = new int[arr.length][arr.length];
int[][] sArr = new int[arr.length][arr.length];
for (int i = 0; i < arr.length; i++) {
fArr[i][i] = arr[i];
}
for (int i = arr.length - 2; i >= 0; i--) {
for (int j = i + 1; j < arr.length; j++) {
fArr[i][j] = Math.max(arr[i] + sArr[i + 1][j], arr[j] + sArr[i][j - 1]);
sArr[i][j] = Math.min(fArr[i + 1][j], fArr[i][j - 1]);
}
}
return Math.max(fArr[0][arr.length - 1], sArr[0][arr.length - 1]);
}
public static void main(String[] args) {
System.out.println(cardsInLine(new int[]{1, 2, 100, 4}));
System.out.println(cardsInLine(new int[]{1, 100, 2}));
System.out.println(cardsInLine(new int[]{19, 92, 12, 17, 56}));
}
}
结果
101
100
109
象棋中马的跳法
请同学们自行搜索或者想象一个象棋的棋盘，然后把整个棋盘放入第一象限，棋盘的最左下角是 (0,0) 位置。那么整个棋盘就是横坐标上 9 条线、纵坐标上10条线的一个区域。给你三个参数：x、y、k，返回如果 马 从 (0,0) 位置出发，必须走 k 步，最后落在 (x, y) 上的方法数有多少种？
递归实现
public class HorseJump {
static int horseJump(int x, int y, int k) {
return process(x, y, k, 0, 0);
}
/**
* @param k 还能走几步
* @param curX 当前走到的 x 坐标
* @param curY 当前走到的 y 坐标
* @return
*/
static int process(int x, int y, int k, int curX, int curY) {
if (k == 0) return x == curX && y == curY ? 1 : 0;
if (curX < 0 || curY < 0 || curX > 9 || curY > 10) return 0;
return process(x, y, k - 1, curX + 1, curY + 2)
+ process(x, y, k - 1, curX + 1, curY - 2)
+ process(x, y, k - 1, curX - 1, curY + 2)
+ process(x, y, k - 1, curX - 1, curY - 2)
+ process(x, y, k - 1, curX + 2, curY + 1)
+ process(x, y, k - 1, curX + 2, curY - 1)
+ process(x, y, k - 1, curX - 2, curY + 1)
+ process(x, y, k - 1, curX - 2, curY - 1);
}
public static void main(String[] args) {
System.out.println(horseJump(1, 2, 3));
System.out.println(horseJump(1, 2, 5));
System.out.println(horseJump(0, 0, 2));
}
}
结果：
8
132
2
另一个思路：
从 (0,0) 位置出发，必须走 k 步，最后落在 (x, y) 上。实际上和 从 (x, y) 位置出发，必须走 k 步，最后落在 (0, 0) 上一样。
代码实现：
public static int process(int x, int y, int step) {
if (x < 0 || x > 8 || y < 0 || y > 9) {
return 0;
}
if (step == 0) {
return (x == 0 && y == 0) ? 1 : 0;
}
return process(x - 1, y + 2, step - 1)
+ process(x + 1, y + 2, step - 1)
+ process(x + 2, y + 1, step - 1)
+ process(x + 2, y - 1, step - 1)
+ process(x + 1, y - 2, step - 1)
+ process(x - 1, y - 2, step - 1)
+ process(x - 2, y - 1, step - 1)
+ process(x - 2, y + 1, step - 1);
}
动态规划
思路：
影响结果的因素有 3 个变量：x、y、k，也就是说需要一个三维数组 int[9][10][k+1]。
根据递归代码逻辑：只有 [0][0][0] 时值为 1，其他 [x][y][0] 都为 0。
请在脑海中想象一个长为 9，宽为 10，高为 k+1 的立方体。第一层只有 [0][0][0] 值为 1，其他 [x][y][0] 都为 0。
根据代码逻辑第二层就相当于第一层的 [x+1][y+2][0] + [x+1][y-2][0] + [x-1][y+2][0] + [x-1][y-2][0] + [x+2][y+1][0] + [x-2][y+1][0] + [x+2][y-1][0] + [x-2][y-1][0] 的结果
这样其他层的结果就都得到了，只需要返回 [x][y][k] 的值即可
代码实现：
public class HorseJump1 {
static int horseJump(int x, int y, int k) {
int[][][] dp = new int[9][10][k + 1];
dp[0][0][0] = 1;
for (int step = 1; step < k + 1; step++) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 10; j++) {
dp[i][j][step] = getValue(dp, i + 1, j + 2, step - 1)
+ getValue(dp, i - 1, j + 2, 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 + 2, j - 1, step - 1)
+ getValue(dp, i - 2, j - 1, step - 1);
}
}
}
return dp[x][y][k];
}
private static int getValue(int[][][] dp, int x, int y, int k) {
if (x < 0 || x >= 9 || y < 0 || y >= 10) return 0;
return dp[x][y][k];
}
public static void main(String[] args) {
System.out.println(horseJump(1, 2, 3));
System.out.println(horseJump(1, 2, 5));
System.out.println(horseJump(0, 0, 2));
}
}
Bob的生存概率
给定五个参数 n、m、i、j、k。表示在一个 n * m 的区域，Bob 处在 (i, j) 点，每次 Bob 等概率的向上、下、左、右四个方向移动一步，Bob 必须走 K 步。如果走完之后，Bob 还停留在这个区域上，就算 Bob 存活，否则就算 Bob 死亡。请求解 Bob 的生存概率，返回字符串表示分数的方式。
递归实现
public class BobDie {
static void bobDie(int m, int n, int i, int j, int k) {
Data data = process(m, n, i, j, k);
System.out.println(data.life + "/" + (data.life + data.death));
}
static class Data {
int life;
int death;
public Data() {
}
public Data(int life, int death) {
this.life = life;
this.death = death;
}
}
static Data process(int m, int n, int i, int j, int k) {
if (k == 0) {
Data data = new Data();
if (i - m > 0 || m - i > m || j - n > 0 || n - j > n) {
data.death = 1;
} else {
data.life = 1;
}
return data;
}
Data d1 = process(m, n, i + 1, j, k - 1);
Data d2 = process(m, n, i - 1, j, k - 1);
Data d3 = process(m, n, i, j + 1, k - 1);
Data d4 = process(m, n, i, j - 1, k - 1);
return new Data(d1.life + d2.life + d3.life + d4.life, d1.death + d2.death + d3.death + d4.death);
}
public static void main(String[] args) {
bobDie(2, 2, 0, 0, 2);
bobDie(2, 2, 1, 1, 2);
}
}
动态规划
还可以根据数学知识，Bob 走 k 步，范围为，也就是在
public class BobDie1 {
static void bobDie(int m, int n, int i, int j, int k) {
int[][][] dp = new int[m + 1][n + 1][k + 1];
dp[i][j][0] = 1;
int life = 0;
for (int step = 1; step <= k; step++) {
for (int a = 0; a <= m; a++) {
for (int b = 0; b <= n; b++) {
dp[a][b][step] = getValue(m, n, step - 1, a, b + 1, dp)
+ getValue(m, n, step - 1, a, b - 1, dp)
+ getValue(m, n, step - 1, a + 1, b, dp)
+ getValue(m, n, step - 1, a - 1, b, dp);
if (step == k) life += dp[a][b][step];
}
}
}
System.out.println(life + "/" + (int) Math.pow(4, k));
}
private static int getValue(int m, int n, int step, int a, int b, int[][][] dp) {
if (a > m || a < 0 || b > n || b < 0) {
return 0;
}
return dp[a][b][step];
}
public static void main(String[] args) {
bobDie(10, 10, 3, 2, 5);
bobDie(2, 2, 1, 1, 2);
}
}
若有收获，就点个赞吧
0 人点赞
