問題問法:
Q:現(xiàn)在有4種硬幣，面值分別為1昌腰、2开伏、5、10分遭商，如果要組成一毛3可以有多少種組法?
Q:一個(gè)人上臺(tái)階的時(shí)候一次可以跨1固灵、2、5級(jí)臺(tái)階劫流，如果臺(tái)階有13級(jí)他有多少種走法?
實(shí)質(zhì)都是求用n種數(shù)字組合成數(shù)值m燒腦預(yù)警:
因?yàn)槲冶磉_(dá)不太好巫玻，大家可能看的不是很懂，可以再看看
https://blog.csdn.net/u013074465/article/details/48575585
雖然我看這個(gè)文章時(shí)候也花了點(diǎn)時(shí)間想一些細(xì)節(jié)祠汇，畢竟這個(gè)問題真的三言兩語講不清楚
如果往下的時(shí)候看不懂仍秤，回到下一行來看看這段話:
===========================================================================
題目的問題實(shí)際上就是求dp[m][sum]，即用前m種硬幣（所有硬幣）構(gòu)成sum的所有組合數(shù)可很。
設(shè)最后一種硬幣的數(shù)量為xn诗力。
當(dāng)xn=0時(shí)，有多少種組合呢我抠？ 實(shí)際上就是前i-1種硬幣組合sum苇本，有dp[i-1][sum]種导坟！
xn = 1 時(shí)呢，有多少種組合圈澈？ 實(shí)際上是用前i-1種硬幣組合成(sum - Vm)的組合數(shù)惫周，有dp[i-1][sum -Vm]種;
xn = 2 呢， dp[i-1][sum - 2 * Vm]種康栈，等等递递。
所有的這些情況加起來就是我們要求的dp[i][sum]。
===========================================================================動(dòng)態(tài)規(guī)劃的概念:
將一個(gè)多階段問題轉(zhuǎn)化成一系列的單階段問題轉(zhuǎn)化講解:
用上面的問題做例子啥么，用4種數(shù)字相加成目標(biāo)值登舞，多階段的解法無非就是暴力枚舉多層for循環(huán)鑲嵌，
這樣很復(fù)雜也不是個(gè)聰明方法悬荣，但是把這一層一層for簡化一下菠秒，轉(zhuǎn)換一下思路
比如你要求用2種數(shù)字組合成一個(gè)數(shù)值13(假設(shè)數(shù)字為1和2)，這里把用i種數(shù)值的組合成數(shù)值j的情況設(shè)為數(shù)組dp[i][j];
那么其實(shí)就是
dp[2][13]=dp[1][13-0x2]+dp[1][13-1x2]+dp[1][13-2x2]+...+dp[1][13-6x2];
為什么是這樣呢,我來解釋下里面的意思氯迂，dp[1][13-0x2]這個(gè)就是當(dāng)數(shù)字2的個(gè)數(shù)為0的時(shí)候的組合數(shù)践叠，
那么dp[1][13-1x2]就是當(dāng)數(shù)字2的數(shù)量為1的時(shí)候的組合數(shù)，為什么到6就停了呢?因?yàn)橛?去組合的話最多
只能用6個(gè)2嚼蚀，7個(gè)的話2x7=14已經(jīng)超過目標(biāo)數(shù)值了禁灼，這里就是把多個(gè)階段給分解成了一個(gè)階段，也就將
求法隱式地轉(zhuǎn)成了利用數(shù)字2個(gè)數(shù)組合地可能性求答案轿曙。
簡化了一層for的求值:
int target=13;
int last_coin=2;
for(int k=0;k<=target/last_coin;++k)
{
dp[last_coin][target]+=dp[last_coin-1][target-k*last_coin];
}
看完代碼就有人會(huì)問弄捕，那d[1][target-k*last_coin]的值從哪里來?那當(dāng)然是根據(jù)d[0][target-k * last_coin]的值累積來的,那么d[0][target-k * last_coin]的值又從哪里來?朋友們，0的時(shí)候是在求問題“用0種硬幣求目標(biāo)數(shù)值可能性有多少種”的答案了导帝，答案當(dāng)然是1守谓，你要用0種硬幣求一個(gè)數(shù)值，那么所有的組合只有一種您单，數(shù)值是0斋荞，各種硬幣的數(shù)量也為0.
- 代碼
#include<iostream>
using namespace std;
int main(){
int coins[4]={1,2,5,10};//硬幣種類數(shù)組
const int coin_kinds_num=sizeof(coins)/sizeof(coins[0]);
const int total=13;//要組合成的目標(biāo)數(shù)值
/*以上為條件：硬幣種類和要組合成的目標(biāo)數(shù)值*/
int dp[coin_kinds_num][total+1];
for(int i=0;i<coin_kinds_num;i++)
{
dp[i][0]=1;
}
/*以上為初始化特殊情況(后面計(jì)算要用)當(dāng)要組合成的目標(biāo)數(shù)值為0的時(shí)候，只有一種情況睹限，那就是各種硬幣的搭配都是0個(gè)*/
for(int i=1;i<=coin_kinds_num;++i)//這里i從1開始,因?yàn)橐呀?jīng)跳過了特殊情況譬猫，而且也不會(huì)組合目標(biāo)數(shù)值0
{
for(int j=1;j<=total;++j)//
{
dp[i][j]=0;//數(shù)組未初始化的時(shí)候值是隨機(jī)數(shù)讯檐，這里初始化一下
for(int k=0;k<=j/coins[i-1];++k)//這里的j/coins[i-1]是指用i種硬幣去組合目標(biāo)時(shí),最多可以放多少個(gè)coins[i-1]這種硬幣
{
dp[i][j]+=dp[i-1][j-k*coins[i-1]];
}
}
}
return 0;
}
