机器人达到指定位置方法数 & 换钱最少的货币数

机器人达到指定位置方法数

题目：机器人达到指定位置方法数

《程序员代码面试指南》第59题 P192 难度：尉★★☆☆

书上题目顺序安排极不合理，这题应该放在上一题的前面。上一题没做出来，大致看了下解析，对这题有一定启发，很快想出来了。

主要介绍一下本题提出的“用暴力递归解决的方法如何优化成动态规划”的套路。

首先是暴力递归方法：

// N : 位置为1 ~ N，固定参数
// cur : 当前在cur位置，可变参数
// rest : 还剩res步没有走，可变参数
// P : 最终目标位置是P，固定参数
// 该函数的含义：只能在1~N这些位置上移动，当前在cur位置，走完rest步之后，停在P位置的方法数作为返回值返回
public int walk(int N, int cur, int rest, int P) {
    // 如果没有剩余步数了，当前的cur位置就是最后的位置
    // 如果最后的位置停在P上，那么之前做的移动是有效的
    // 如果最后的位置没在P上，那么之前做的移动是无效的
    if (rest == 0) {
        return cur == P ? 1 : 0;
    }
    // 如果还有rest步要走，而当前的cur位置在1位置上，那么当前这步只能从1走向2
    // 后续的过程就是，来到2位置上，还剩rest-1步要走
    if (cur == 1) {
        return walk(N, 2, rest - 1, P);
    }
    // 如果还有rest步要走，而当前的cur位置在N位置上，那么当前这步只能从N走向N-1
    // 后续的过程就是，来到N-1位置上，还剩rest-1步要走
    if (cur == N) {
        return walk(N, N - 1, rest - 1, P);
    }
    // 如果还有rest步要走，而当前的cur位置在中间位置上，那么当前这步可以走向左，也可以走向右
    // 走向左之后，后续的过程就是，来到cur-1位置上，还剩rest-1步要走
    // 走向右之后，后续的过程就是，来到cur+1位置上，还剩rest-1步要走
    // 走向左、走向右是截然不同的方法，所以总方法数要都算上
    return walk(N, cur + 1, rest - 1, P) + walk(N, cur - 1, rest - 1, P);
}

public int ways1(int N, int M, int K, int P) {
    // 参数无效直接返回0
    if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
        return 0;
    }
    // 总共N个位置，从M点出发，还剩K步，返回最终能达到P的方法数
    return walk(N, M, K, P);
}

套路大体步骤如下：

前提：你的尝试过程是无后效性的。所谓无后效性，是指一个递归状态的返回值与怎么到达这个状态的路径无关。某个无后效性的递归过程（尝试过程）一旦确定，怎么优化成动态规划是有固定套路的。

1. 找到什么可变参数可以代表一个递归状态，也就是哪些参数一旦确定，返回值就确定了。
   
2. 把可变参数的所有组合映射成一张表，有1个可变参数就是一维表，2个可变参数就是二维表……
   
3. 最终答案要的是表中的哪个位置，在表中标出。
   
4. 根据递归过程的base case，把这张表最简单、不需要依赖其他位置的那些位置填好值。
   
5. 根据递归过程非base case的部分，也就是分析表中的普遍位置需要怎么计算得到，那么这张表的填写顺序也就确定了。
   
6. 填好表，返回最终答案在表中位置的值。

本题是满足前提——无后效性的，本题运用该套路的详细流程见书P195-197。

填写每一个位置的值都是O(1)的时间复杂度，所以总的时间复杂度为O(N×K)。

public int ways2(int N, int M, int K, int P) {
    // 参数无效直接返回0
    if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
        return 0;
    }
    int[][] dp = new int[K + 1][N + 1];
    dp[0][P] = 1;
    for (int i = 1; i <= K; i++) {
        for (int j = 1; j <= N; j++) {
            if (j == 1) {
                dp[i][j] = dp[i - 1][2];
            } else if (j == N) {
                dp[i][j] = dp[i - 1][N - 1];
            } else {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
            }
        }
    }
    return dp[K][M];
}

以及动态规划+空间压缩的解法：

public int ways3(int N, int M, int K, int P) {
    // 参数无效直接返回0
    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 i = 1; i <= K; i++) {
        int leftUp = dp[1];// 左上角的值
        for (int j = 1; j <= N; j++) {
            int tmp = dp[j];
            if (j == 1) {
                dp[j] = dp[j + 1];
            } else if (j == N) {
                dp[j] = leftUp;
            } else {
                dp[j] = leftUp + dp[j + 1];
            }
            leftUp = tmp;
        }
    }
    return dp[M];
}

另外需要注意，对于有后效性的尝试过程，本套路是失效的，不过这类题目在面试中出现的概率极低。

换钱最少的货币数

题目：换钱最少的货币数

《程序员代码面试指南》第58题 P189 难度：尉★★☆☆

此题为“暴力递归优化成动态规划”套路的第2题。

先想暴力尝试的方法，然后优化成动态规划。只有想出尝试方法是最难、最重要的。

暴力尝试过程如下，每一种面值都尝试不同的张数。从arr[0]开始依次往右考虑所有面值。

public int minCoins1(int[] arr, int aim) {
    if (arr == null || arr.length == 0 || aim < 0) {
        return -1;
    }
    return process(arr, 0, aim);
}

// 当前考虑的面值是arr[i]，还剩rest的钱需要找零
// 如果返回-1说明自由使用arr[i..N-1]面值的情况下，无论如何也无法找零rest
// 如果返回不是-1，代表自由使用arr[i..N-1]面值的情况下，找零rest需要的最少张数
public int process(int[] arr, int i, int rest) {
    // base case：
    // 已经没有面值能够考虑了
    // 如果此时剩余的钱为0，返回0张
    // 如果此时剩余的钱不是0，返回-1
    if (i == arr.length) {
        return rest == 0 ? 0 : -1;
    }
    // 最少张数，初始时为-1，因为还没找到有效解
    int res = -1;
    // 依次尝试使用当前面值(arr[i])0张、1张、k张，但不能超过rest
    for (int k = 0; k * arr[i] <= rest; k++) {
        // 使用了k张arr[i]，剩下的钱为rest - k * arr[i]
        // 交给剩下的面值去搞定(arr[i+1..N-1])
        int next = process(arr, i + 1, rest - k * arr[i]);
        if (next != -1) { // 说明这个后续过程有效
            res = res == -1 ? next + k : Math.min(res, next + k);
        }
    }
    return res;
}

优化套路过程如下：

前提：尝试过程是无后效性的。（使用2张5元、0张2元和使用0张5元、5张2元，后续过程process(arr,2,90)，这个状态返回值是一样的，说明一个状态最终的返回值与怎么达到这个状态的过程无关）。

1. 可变参数i和rest。
2. 组合成一张二维表，N行aim列。i范围[0,N]，rest范围[0,aim]。
3. 最终状态是process(arr,0,aim)，即dp[0][aim]，位于dp表0行最后一列。
4. 填写初始位置，最后一行只有dp[N][0]是0，其它位置都是-1。
5. 填写普遍位置。因为dp[i][rest]的值为：dp[i+1][rest-0*arr[i]]+0、dp[i+1][rest-1*arr[i]]+1、dp[i+1][rest-2*arr[i]]+2、……dp[i+1][rest-k*arr[i]]+k、……直到越界，而在求dp[i][rest]之前，dp[i][rest-arr[i]]已经求过了，为：dp[i+1][rest-1*arr[i]]+0、dp[i+1][rest-2*arr[i]]+1、……dp[i+1][rest-k*arr[i]]+k-1、……直到越界。可以得到：dp[i][rest]=min{dp[i][rest-arr[i]]+1, dp[i+1][rest]}。所以，dp[i][rest]只依赖下面一个位置（dp[i+1][rest]）和左边一个位置（dp[i][rest-arr[i]]+1）。最后一排的值已经有了，再从左往右求出倒数第二排、倒数第三排……直到第一排即可。
6. 最后返回dp[0][aim]位置的值就是答案。

public int minCoins2(int[] arr, int aim) {
    if (arr == null || arr.length == 0 || aim < 0) {
        return -1;
    }
    int N = arr.length;
    int[][] dp = new int[N + 1][aim + 1];
    // 设置最后一排的值，除了dp[N][0]为0之外，其他都是-1
    for (int col = 1; col <= aim; col++) {
        dp[N][col] = -1;
    }
    for (int i = N - 1; i >= 0; i--) { // 从底往上计算每一行
        for (int rest = 0; rest <= aim; rest++) { // 每一行都从左往右
            dp[i][rest] = -1; // 初始时先设置dp[i][rest]的值无效
            if (dp[i + 1][rest] != -1) { // 下面的值如果有效
                dp[i][rest] = dp[i + 1][rest]; // dp[i][rest]的值先设置成下面的值
            }
            // 左边的位置不越界并且有效
            if (rest - arr[i] >= 0 && dp[i][rest - arr[i]] != -1) {
                if (dp[i][rest] == -1) { // 如果之前下面的值无效
                    dp[i][rest] = dp[i][rest - arr[i]] + 1;
                } else { // 说明下面和左边的值都有效，取最小的
                    dp[i][rest] = Math.min(dp[i][rest],
                                           dp[i][rest - arr[i]] + 1);
                }
            }
        }
    }
    return dp[0][aim];
}

因为省掉了枚举过程，所以每个位置的值都在O(1)时间内得到，时间复杂度就为O(N×aim)。同样可以参照“矩阵的最小路径和”使用空间压缩。

本题感觉是比上面一题更难一点，主要是这个二维表的行和列的意义很难想到，所以还是得先想出暴力递归的尝试过程，然后再优化成动态规划。