算法基础之暴力递归到动态规划，java 程序员面试算法宝典 pdf 猿媛之家
题目二
===
假设有排成一行的 N 个位置，记为 1~N,N 一定大于或等于 2
开始时机器人在其中的 M 位置上(M 一定是 1~N 中的一个)
如果机器人来到 1 位置，那么下一步只能往右来到 2 位置;
如果机器人来到 N 位置，那么下一步只能往左来到 N-1 位置﹔
如果机器人来到中间位置，那么下一步可以往左走或者往右走;
规定机器人必须走 K 步，最终能来到 P 位置(P 也是 1~N 中的一个)的方法有多少种
给定四个参数 N、M、K、P，返回方法数。
递归方法：
package com.zh.class18;
public class RobotWalk {
public static void main(String[] args) {
System.out.println(ways(4, 2, 4, 4));
}
public static int ways(int N, int M, int K, int P) {
if (N < 2 || M < 1 || M > N || P < 1 || P > N || K < 1) {
return -1;
}
return process(M, K, P, N);
}
/**
@param cur 当前的位置
@param rest 剩余的步数
@param aim 目标位置
@param N 所有的位置数目
@return 返回满足的数目
*/
private static int process(int cur, int rest, int aim, int N) {
if (rest == 0) {
return cur == aim ? 1 : 0;
}
if (cur == 1) {
return process(2, rest - 1, aim, N);
}
if (cur == N) {
return process(N - 1, rest - 1, aim, N);
}
return process(cur - 1, rest - 1, aim, N) + process(cur + 1, rest - 1, aim, N);
}
}
从递归中可以看出 cur 和 rest 是决定递归的 key 值，并且有重复过程，那么可以使用缓存的方法(即记忆化搜索)：
cur 的范围是 1?~ N，rest 的范围是 0 ~ K
package com.zh.class18;
public class RobotWalk {
public static void main(String[] args) {
System.out.println(ways(4, 2, 4, 4));
System.out.println(ways1(4, 2, 4, 4));
}
public static int ways1(int N, int M, int K, int P) {
if (N < 2 || M < 1 || M > N || P < 1 || P > 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;
}
}
return process1(M, K, P, N, dp);
}
/**
@param cur 当前的位置 范围是 1 ~ N
@param rest 剩余的步数 范围是 0 ~ K
@param aim 目标位置
@param N 所有的位置数目
@return 返回满足的数目
*/
private static int process1(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 = process1(2, rest - 1, aim, N, dp);
} else if (cur == N) {
ans = process1(N - 1, rest - 1, aim, N, dp);
} else {
ans = process1(cur - 1, rest - 1, aim, N, dp) + process1(cur + 1, rest - 1, aim, N, dp);
}
dp[cur][rest] = ans;
return ans;
}
}
再次优化为动态规划：
public static int ways2(int N, int M, int K, int P) {
if (N < 2 || M < 1 || M > N || P < 1 || P > N || K < 1) {
return -1;
}
int[][] dp = new int[N + 1][K + 1];
dp[P][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[M][K];
}
题目三：
====
给定一个整型数组 arr，代表数值不同的纸牌排成一条线
玩家 A 和玩家 B 依次拿走每张纸牌
规定玩家 A 先拿，玩家 B 后拿，但是每个玩家每次只能拿走最左或最右的纸牌
玩家 A 和玩家 B 都绝顶聪明
请返回最后获胜者的分数。
暴力递归方法：
package com.zy.class002;
public class
CardsInLine {
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));
}
// 根据规则，返回获胜者的分数
public static int win1(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int first = first(arr, 0, arr.length - 1);
int second = after(arr, 0, arr.length - 1);
return Math.max(first, second);
}
// 先手获得的分数
public static int first(int[] arr, int left, int right) {
if (left == right) {
return arr[left];
还未添加个人签名 2021.03.18 加入
还未添加个人简介
评论