package com.jiucaiyuan.net.question;
/**
* @Author jiucaiyuan 2022/6/5 10:34
* @mail services@jiucaiyuan.net
*/
public class Rabbit {
/**
* 给了一个固定值n，表示总共有多少个位置
* 开始机器人在s位置上，每次可以迈一步，想要到达e位置，总共要走k步，有多少种走法可以到达e位置
* 机器人可以往左走，也可以往右走
*
* @param n 总共位置数 1 2 3 4 ... n
* @param s start开始位置（机器人开始停在s位置）
* @param e end目标位置 （迈k步后，停留在e位置）
* @param k 迈的步数 （机器人必须走k步）
* @return 总共走法的种数
*/
public static int walkWays(int n, int s, int e, int k) {
return process(n, e, k, s);
}
/**
* 暴力递归实现
* 因为递归过程类似一个二叉树的遍历，高度为k，所以时间复杂度是 O(2^k)
*
* @param n 总共位置1 2 3 4 5 ... n
* @param e 目标位置
* @param rest 当前剩下的步数
* @param curr 当前所在的位置
* @return 当前的走法数目
*/
public static int process(int n, int e, int rest, int curr) {
//当前没有步骤可走了，如果在目标位置上，那么找到1中走法，如果没有在目标位置上，不是合法走法
if (rest == 0) {
return curr == e ? 1 : 0;
}
//如果当前位置在1，那么只能往2位置走
if (rest == 1) {
return process(n, e, rest - 1, 2);
}
//如果当前位置在n，那么下一步只能走到n-1
if (rest == n) {
return process(n, e, rest - 1, n - 1);
}
//如果不在第一个位置，也不在最后一个位置，那么可以向左走一步，也可以往右走一步
return process(n, e, rest - 1, curr - 1) + process(n, e, rest - 1, curr + 1);
}
/**
* 给了一个固定值n，表示总共有多少个位置
* 开始机器人在s位置上，每次可以迈一步，想要到达e位置，总共要走k步，有多少种走法可以到达e位置
* 机器人可以往左走，也可以往右走
* 优化版本，暴力递归中重复的操作用缓存空间换时间的方式优化掉
*
* @param n 总共位置数 1 2 3 4 ... n
* @param s start开始位置（机器人开始停在s位置）
* @param e end目标位置 （迈k步后，停留在e位置）
* @param k 迈的步数 （机器人必须走k步）
* @return 总共走法的种数
*/
public static int walkWaysV2(int n, int s, int e, int k) {
int[][] dp = new int[k + 1][n + 1];
for (int i = 0; i <= k; i++) {
for (int j = 0; j <= n; j++) {
dp[i][j] = -1;
}
}
return processV2(n, e, k, s, dp);
}
/**
* 用空间换取暴力递归中重复计算的一些值
* 时间复杂度: O(k*n)
*
* @param n 总共位置1 2 3 4 5 ... n
* @param e 目标位置
* @param rest 当前剩下的步数
* @param curr 当前所在的位置
* @param dp 计算过的值记录起来
* @return 当前的走法数目
*/
public static int processV2(int n, int e, int rest, int curr, int[][] dp) {
if (dp[rest][curr] != -1) {
return dp[rest][curr];
}
//当前没有步骤可走了，如果在目标位置上，那么找到1中走法，如果没有在目标位置上，不是合法走法
if (rest == 0) {
dp[rest][curr] = curr == e ? 1 : 0;
} else if (rest == 1) {
//如果当前位置在1，那么只能往2位置走
dp[rest][curr] = process(n, e, rest - 1, 2);
} else if (rest == n) {
//如果当前位置在n，那么下一步只能走到n-1
dp[rest][curr] = process(n, e, rest - 1, n - 1);
} else {
//如果不在第一个位置，也不在最后一个位置，那么可以向左走一步，也可以往右走一步
dp[rest][curr] = process(n, e, rest - 1, curr - 1) + process(n, e, rest - 1, curr + 1);
}
return dp[rest][curr];
}
/**
* 动态规划方式实现
* 其实是分析上述递归过程，发现递归过程的规律，改为二维数组dp的前后联系，转化为dp二维数组的求解过程
* （动态转移方程，其实就是上述递归的过程，也是分析尝试的过程）
* 时间复杂度 O(k*n)
*
* @param n 总共可选位置1 2 3 4 ... n
* @param e 目标位置
* @param s 开始位置
* @param k 需要移动步数
* @return 返回走法数目
*/
public static int dpWay(int n, int e, int s, int k) {
int[][] dp = new int[k + 1][n + 1];
dp[0][e] = 1;
for (int rest = 1; rest <= k; rest++) {
for (int curr = 1; curr <= n; curr++) {
if (curr == 1) {
dp[rest][curr] = dp[rest - 1][2];
} else if (curr == n) {
dp[rest][curr] = dp[rest - 1][curr - 1];
} else {
dp[rest][curr] = dp[rest - 1][curr - 1] + dp[rest - 1][curr + 1];
}
}
}
return dp[s][k];
}
}