算法思想之动态规划(三)——找零钱问题

2019-05-31 本文已影响0人复旦猿

前言

今天我们继续讨论经典的动态规划问题之找零钱问题。

找零钱问题

问题描述

假设你是一名超市收银员，现有 $n$ 种不同面值的货币，每种面值的货币可以使用任意张。顾客结账时，你需要找给顾客 $aim$ 元零钱，你可以给出多少种方法。例如，有1、2、3元三种面值的货币，你需要找零3元，那么共有3种方法：1张1元+1张2元、3张1元、1张3元。

问题分析

假设长度为 $n$ 的一维数组 $penny$ ，其中每个元素对应每种货币的面值。找零钱问题可以抽象为使用 $penny$ 中的元素可以有多少种方法组成数值 $aim$ 。
简单的，我们可以遍历数组，对下标 $index$ 的元素使用 $i$ ( $0 \leq i \leq aim / penny[index]$ )次, 计算剩余的数组元素和剩余数值满足要求的方法数。把每一次的方法数相加求和即为该问题的解。不难发现，每一次要求解的都是和父问题具有同样性质的子问题，即使用 $penny[index:n-1]$ 中的元素有多少种方法组成数值 $aim - i * penny[index]$ 。
由此，很容易写出该问题的暴力搜索（即递归）方法和记忆搜索方法。但是如果要直接写出动态规划的状态转移方程可能需要费点功夫。不过，我们可以按照算法思想之动态规划(一)讨论的动态规划的一般步骤进行思考。
(1)划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
(2)确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
(3)确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
(4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。

对于上面4条，我们一一来看。
(1) 划分阶段
构造有序或可排序的阶段，要求我们计算的时候肯定当前计算结果依赖于前面阶段的结果。如果问题中的 $aim=3$ ， $penny = [1, 2, 3]$ ，如何划分阶段呢？对于 $penny$ 来说，可按照下标进行划分，即 $1,2,3$ 这3个阶段；对于 $aim$ 来说，由于每一阶段下都要求 $aim$ 是非负整数，那么我们可以划分为 $0-aim$ ，即 $0，1，2，3$ 这4个阶段。
(2) 确定状态和状态变量
由第(1)步，我们可以得到一个的 $n \times (aim+1)$ 的矩阵 $dp$ ，每个矩阵元素 $dp[i][j]$ 代表的含义是使用数组 $penny$ 前 $i$ 个元素组成数值 $j$ 的方法总数。
(3) 确定决策并写出状态转移方程
由第(2)步总结可得出规律： $dp[i][j] = dp[i-1][j] + dp[i-1][j-penny[i]] + ... + dp[i-1][j-k*penny[i]].$ 例如：仍然以(1)中的问题为例， $dp[1][2] = dp[0][2] + dp[0][2-1*1])$ ，代表使用 $penny$ 前2个元素(即 $1，2$ )组成2的方法数 = 不使用2组成2的方法数 + 使用1个2组成2的方法数。
其实，对于该状态转移方程还可以继续优化：令 $z = j-penny[i]$ 由于 $dp[i][z] = dp[i-1][z] + dp[i-1][z - penney[i]] +... + dp[i-1][z-k' *penny[i]]$ ，可以看出 $dp[i][z]$ 与 $dp[i][j]$ 展开式中第2项之后的值是一样的，因此状态方程可化简为： $dp[i][j] = dp[i-1][j] + dp[i][j-penny[i]]$
(4) 寻找边界条件
由第(3)步，可得到化简前的边界条件为： $j-k*penny[i] \geq 0$ ，化简后的边界条件为： $j-penny[i] \geq 0$ 。
总结来看，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）。

代码实现

public class Exchange {
    // 用于记忆搜索的计算过的方案
    public static HashMap<String, Integer> map = new HashMap<>();

    public static int countWays(int[] penny, int n, int aim) {
        if (0 == n || null == penny || aim <= 0) {
            return 0;
        }
        // return core1(penny, 0, aim);
        // return core2(penny, 0, aim);
        // return core3(penny, n, aim);
        return core4(penny, n, aim);
    }

    /**
     * 暴力搜索
     * @param penny
     * @param index
     * @param aim
     * @return
     */
    public static int core1(int[] penny, int index, int aim) {
        int result = 0;
        if (index == penny.length) {
            result = aim == 0 ? 1 : 0;
        } else {
            for (int i = 0; i * penny[index] <= aim; i++) {
                result += core1(penny, index + 1, aim - i * penny[index]);
            }
        }
        return result;
    }

    /**
     * 记忆搜索
     * @param penny
     * @param index
     * @param aim
     * @return
     */
    public static int core2(int[] penny, int index, int aim) {
        String key = String.valueOf(index) + "_" + String.valueOf(aim);
        if (map.containsKey(key)) {
            return map.get(key);
        }
        int result = 0;
        if (index == penny.length) {
            result = aim == 0 ? 1 : 0;
        } else {
            for (int i = 0; i * penny[index] <= aim; i++) {
                result += core2(penny, index + 1, aim - i * penny[index]);
            }
        }
        map.put(key, result);
        return result;
    }

    /**
     * 动态规划
     * @param penny
     * @param n
     * @param aim
     * @return
     */
    public static int core3(int[] penny, int n, int aim) {
        int[][] dp = new int[n][aim + 1];
        for (int i = 0; i < aim + 1; i++) {
            dp[0][i] = i % penny[0] == 0 ? 1 : 0;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < aim + 1; j++) {
                for (int m = 0; m * penny[i] <= j; m++) {
                    dp[i][j] += dp[i - 1][j - m * penny[i]];
                }
            }
        }
        return dp[n-1][aim];
    }

    /**
     * 动态规划优化
     * @param penny
     * @param n
     * @param aim
     * @return
     */
    public static int core4(int[] penny, int n, int aim) {
        int[][] dp = new int[n][aim + 1];
        for (int i = 0; i < aim + 1; i++) {
            dp[0][i] = i % penny[0] == 0 ? 1 : 0;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < aim + 1; j++) {
                if (j < penny[i]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - penny[i]];
                }
            }
        }
        return dp[n - 1][aim];
    }

    public static void main(String[] args) {
        int[] penny = new int[]{3, 4, 7};
        int n = penny.length;
        int aim = 33;
        System.out.println(countWays(penny, n, aim));
    }
}

其他经典问题

未来几篇博文，我将继续对经典的动态规划问题进行整理，敬请关注~
由于本人水平有限，文章难免有欠妥之处，欢迎大家多多批评指正！

写在最后

欢迎大家关注我的个人博客复旦猿。