前言

今天我們繼續(xù)討論經(jīng)典的動(dòng)態(tài)規(guī)劃問題之找零錢問題。

找零錢問題

問題描述

假設(shè)你是一名超市收銀員，現(xiàn)有種不同面值的貨幣，每種面值的貨幣可以使用任意張。顧客結(jié)賬時(shí)，你需要找給顧客元零錢，你可以給出多少種方法。例如，有1、2、3元三種面值的貨幣，你需要找零3元，那么共有3種方法：1張1元+1張2元、3張1元、1張3元。

問題分析

假設(shè)長(zhǎng)度為的一維數(shù)組，其中每個(gè)元素對(duì)應(yīng)每種貨幣的面值。找零錢問題可以抽象為使用中的元素可以有多少種方法組成數(shù)值。
簡(jiǎn)單的，我們可以遍歷數(shù)組，對(duì)下標(biāo)的元素使用()次, 計(jì)算剩余的數(shù)組元素和剩余數(shù)值滿足要求的方法數(shù)。把每一次的方法數(shù)相加求和即為該問題的解。不難發(fā)現(xiàn)，每一次要求解的都是和父問題具有同樣性質(zhì)的子問題，即使用中的元素有多少種方法組成數(shù)值。
由此，很容易寫出該問題的暴力搜索（即遞歸）方法和記憶搜索方法。但是如果要直接寫出動(dòng)態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程可能需要費(fèi)點(diǎn)功夫。不過，我們可以按照算法思想之動(dòng)態(tài)規(guī)劃(一)討論的動(dòng)態(tài)規(guī)劃的一般步驟進(jìn)行思考。
(1)劃分階段：按照問題的時(shí)間或空間特征，把問題分為若干個(gè)階段。在劃分階段時(shí)，注意劃分后的階段一定要是有序的或者是可排序的，否則問題就無法求解。
(2)確定狀態(tài)和狀態(tài)變量：將問題發(fā)展到各個(gè)階段時(shí)所處于的各種客觀情況用不同的狀態(tài)表示出來。當(dāng)然，狀態(tài)的選擇要滿足無后效性。
(3)確定決策并寫出狀態(tài)轉(zhuǎn)移方程：因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)。所以如果確定了決策，狀態(tài)轉(zhuǎn)移方程也就可寫出。但事實(shí)上常常是反過來做，根據(jù)相鄰兩個(gè)階段的狀態(tài)之間的關(guān)系來確定決策方法和狀態(tài)轉(zhuǎn)移方程。
(4)尋找邊界條件：給出的狀態(tài)轉(zhuǎn)移方程是一個(gè)遞推式，需要一個(gè)遞推的終止條件或邊界條件。

對(duì)于上面4條，我們一一來看。
(1) 劃分階段
構(gòu)造有序或可排序的階段，要求我們計(jì)算的時(shí)候肯定當(dāng)前計(jì)算結(jié)果依賴于前面階段的結(jié)果。如果問題中的，，如何劃分階段呢？對(duì)于來說，可按照下標(biāo)進(jìn)行劃分，即這3個(gè)階段；對(duì)于來說，由于每一階段下都要求是非負(fù)整數(shù)，那么我們可以劃分為，即這4個(gè)階段。
(2) 確定狀態(tài)和狀態(tài)變量
由第(1)步，我們可以得到一個(gè)的的矩陣，每個(gè)矩陣元素代表的含義是使用數(shù)組前個(gè)元素組成數(shù)值的方法總數(shù)。
(3) 確定決策并寫出狀態(tài)轉(zhuǎn)移方程
由第(2)步總結(jié)可得出規(guī)律：例如：仍然以(1)中的問題為例，，代表使用前2個(gè)元素(即)組成2的方法數(shù) = 不使用2組成2的方法數(shù) + 使用1個(gè)2組成2的方法數(shù)。
其實(shí)，對(duì)于該狀態(tài)轉(zhuǎn)移方程還可以繼續(xù)優(yōu)化：令由于，可以看出與展開式中第2項(xiàng)之后的值是一樣的，因此狀態(tài)方程可化簡(jiǎn)為：
(4) 尋找邊界條件
由第(3)步，可得到化簡(jiǎn)前的邊界條件為：，化簡(jiǎn)后的邊界條件為：。
總結(jié)來看，只要解決問題的階段、狀態(tài)和狀態(tài)轉(zhuǎn)移決策確定了，就可以寫出狀態(tài)轉(zhuǎn)移方程（包括邊界條件）。

代碼實(shí)現(xiàn)

public class Exchange {
    // 用于記憶搜索的計(jì)算過的方案
    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;
    }

    /**
     * 動(dòng)態(tài)規(guī)劃
     * @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];
    }

    /**
     * 動(dòng)態(tài)規(guī)劃優(yōu)化
     * @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));
    }
}

其他經(jīng)典問題

• 算法思想之動(dòng)態(tài)規(guī)劃(二)——最小路徑和問題
• 算法思想之動(dòng)態(tài)規(guī)劃(四)——最長(zhǎng)公共子序列問題
• 算法思想之動(dòng)態(tài)規(guī)劃(五)——最小編輯距離問題
• 算法思想之動(dòng)態(tài)規(guī)劃(六)——最長(zhǎng)上升子序列問題
• 算法思想之動(dòng)態(tài)規(guī)劃(七)——背包問題

未來幾篇博文，我將繼續(xù)對(duì)經(jīng)典的動(dòng)態(tài)規(guī)劃問題進(jìn)行整理，敬請(qǐng)關(guān)注~
由于本人水平有限，文章難免有欠妥之處，歡迎大家多多批評(píng)指正！

寫在最后

歡迎大家關(guān)注我的個(gè)人博客復(fù)旦猿。