前言
今天我們繼續(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è)長度為的一維數(shù)組
新博，其中每個(gè)元素對(duì)應(yīng)每種貨幣的面值。找零錢問題可以抽象為使用
中的元素可以有多少種方法組成數(shù)值
脚草。
簡單的赫悄，我們可以遍歷數(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)方程可化簡為：
(4) 尋找邊界條件
由第(3)步，可得到化簡前的邊界條件為：屿聋，化簡后的邊界條件為：
卵凑。
總結(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ī)劃(四)——最長公共子序列問題
- 算法思想之動(dòng)態(tài)規(guī)劃(五)——最小編輯距離問題
- 算法思想之動(dòng)態(tài)規(guī)劃(六)——最長上升子序列問題
- 算法思想之動(dòng)態(tài)規(guī)劃(七)——背包問題
未來幾篇博文，我將繼續(xù)對(duì)經(jīng)典的動(dòng)態(tài)規(guī)劃問題進(jìn)行整理黑忱，敬請關(guān)注~
由于本人水平有限宴抚，文章難免有欠妥之處，歡迎大家多多批評(píng)指正甫煞！
寫在最后
歡迎大家關(guān)注我的個(gè)人博客復(fù)旦猿菇曲。
