package basic.dynamicprogramming;

/**
 * 机器人移动问题
 * <p>
 * 对于N个格子（从1~N标号），机器人最开始在Start（1<=Start<=N）位置，
 * 要求在走过K（K>=1）步后（一次一格），来到aim位置（1<=aim<=N），
 * 问机器人有多少种走法？（注：在两端的格子只能往中间走，在中间的任意一个格子，可以选择左走或右走）
 * <p>
 * 微信公众号：Java和算法学习
 *
 * @author 周一
 */
public class RobotWalk {

    /**
     * 1.从尝试开始
     */
    public static int way1(int n, int start, int aim, int k) {
        if (n < 2 || start < 1 || start > n || aim < 1 || aim > n || k < 1) {
            return -1;
        }
        return process1(start, k, aim, n);
    }

    /**
     * 计算机器人满足条件的走法有多少种
     *
     * @param current   当前位置
     * @param remaining 剩余步数
     * @param aim       目标位置
     * @param n         格子数
     */
    private static int process1(int current, int remaining, int aim, int n) {
        // base case，不需要走时
        if (remaining == 0) {
            // 剩余步数为0时当前正好在aim位置，则这是一种走法
            return current == aim ? 1 : 0;
        }
        // 还有步数要走
        if (current == 1) {
            // 在最左侧，只能往右走
            return process1(2, remaining - 1, aim, n);
        } else if (current == n) {
            // 在最右侧，只能往左走
            return process1(n - 1, remaining - 1, aim, n);
        } else {
            // 在中间位置，左走或右走都可以，所以是两种情况产生的结果之和
            return process1(current - 1, remaining - 1, aim, n)
                    + process1(current + 1, remaining - 1, aim, n);
        }
    }

    /**
     * 2.傻缓存法
     */
    public static int way2(int n, int start, int aim, int k) {
        if (n < 2 || start < 1 || start > n || aim < 1 || aim > n || k < 1) {
            return -1;
        }
        // 机器人当前位置范围是1~n，剩余步数范围是0~k，dp表(n + 1)*(k + 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;
            }
        }
        // dp[current][remaining] == -1，表示没算过
        // dp[current][remaining] != -1，表示算过，保存的是产生的结果
        return process2(start, k, aim, n, dp);
    }

    /**
     * 计算机器人满足条件的走法有多少种，傻缓存法
     *
     * @param current   当前位置
     * @param remaining 剩余步数
     * @param aim       目标位置
     * @param n         格子数
     */
    private static int process2(int current, int remaining, int aim, int n, int[][] dp) {
        // 缓存表已经有值了，直接返回
        if (dp[current][remaining] != -1) {
            return dp[current][remaining];
        }

        // 之前没算过
        int answer;
        if (remaining == 0) {
            answer = current == aim ? 1 : 0;
        } else if (current == 1) {
            answer =  process2(2, remaining - 1, aim, n, dp);
        } else if (current == n) {
            answer =  process2(n - 1, remaining - 1, aim, n, dp);
        } else {
            answer =  process2(current - 1, remaining - 1, aim, n, dp)
                    + process2(current + 1, remaining - 1, aim, n, dp);
        }

        // 返回前更新缓存
        dp[current][remaining] = answer;
        return dp[current][remaining];
    }

    /**
     * 3.最终版的动态规划
     */
    public static int way3(int n, int start, int aim, int k) {
        if (n < 2 || start < 1 || start > n || aim < 1 || aim > n || k < 1) {
            return -1;
        }
        // 机器人当前位置范围是1~n，剩余步数范围是0~k，dp表(n + 1)*(k + 1)肯定是能够将所有的情况都包含的
        int[][] dp = new int[n + 1][k + 1];
        // 剩余步数为0时，当前位置为aim时为1
        dp[aim][0] = 1;
        for (int remaining = 1; remaining <= k; remaining++) {
            // 第一行，依赖左下方的值
            dp[1][remaining] = dp[2][remaining - 1];
            // 第一行和第n行单独算后，此处就不用判断越界问题了
            for (int current = 2; current <= n - 1; current++) {
                // 非边上的行，依赖左下方和左上方的值
                dp[current][remaining] = dp[current - 1][remaining - 1] + dp[current + 1][remaining - 1];
            }
            // 第n行，依赖左上方的值
            dp[n][remaining] = dp[n - 1][remaining - 1];
        }
        return dp[start][k];
    }

    public static void main(String[] args) {
        // n=5，start=2，aim=4，k=6
        System.out.println("way1: " + way1(5, 2, 4, 6));
        System.out.println("way2: " + way2(5, 2, 4, 6));
        System.out.println("way3: " + way3(5, 2, 4, 6));
    }

}