动态规划习题(一)

假设有排成一行的N个位置记为1~N，N一定大于或等于2
开始时机器人在其中的start位置上(start一定是1~N中的一个)
如果机器人来到1位置，那么下一步只能往右来到2位置；
如果机器人来到N位置，那么下一步只能往左来到N-1位置；
如果机器人来到中间位置，那么下一步可以往左走或者往右走；
规定机器人必须走K步，最终能来到aim位置(P也是1~N中的一个)的方法有多少种
给定四个参数 N，start，aim，K 返回能走到的方法数

public class Code01_RobotWalk {
    public static int ways1(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);
    }

    // 机器人当前来到的位置是cur，
    // 机器人还有rest步需要去走，
    // 最终的目标是aim，
    // 有哪些位置？1~N
    // 返回：机器人从cur出发，走过rest步之后，最终停在aim的方法数，是多少？
    public static int process1(int cur, int rest, int aim, int N) {
        // 当前可走步数为0，表明走完了
        if (rest == 0) {
            // 如果当前走到的位置为aim， 说明路径正确，返回1，否则返回0
            return cur == aim ? 1 : 0;
        }

        // rest > 0,还可以走
        // 如果cur为1，只能向左走
        if (cur == 1) {
            return process1(2, rest - 1, aim, N);
        }
        // 如果cur为N，只能向右走
        if (cur == N) {
            return process1(N - 1, rest - 1, aim, N);
        }
        // 如果在中间，则既可以左走也可以右走
        return process1(cur + 1, rest - 1, aim, N) + process1(cur - 1, rest - 1, aim, N);
    }

    public static int ways2(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];
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= K; j++) {
                dp[i][j] = -1;
            }
        }
        return process2(start, K, aim, N, dp);
    }

    public static int process2(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 = process2(2, rest - 1, aim, N, dp);
        } else if (cur == N) {
            ans = process2(N - 1, rest - 1, aim, N, dp);
        } else {
            ans = process2(cur + 1, rest - 1, aim, N, dp) + process2(cur - 1, rest - 1, aim, N, dp);
        }

        dp[cur][rest] = ans;
        return ans;
    }

    public static int ways3(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(ways1(5, 2, 4, 6));
        System.out.println(ways2(5, 2, 4, 6));
        System.out.println(ways3(5, 2, 4, 6));
    }
}