基本思想：?jiǎn)栴}的最優(yōu)解如果可以由子問(wèn)題的最優(yōu)解推導(dǎo)得到僵刮，則可以先求解子問(wèn)題的最優(yōu)解，在構(gòu)造原問(wèn)題的最優(yōu)解鹦牛；若子問(wèn)題有較多的重復(fù)出現(xiàn)搞糕，則可以自底向上從最終子問(wèn)題向原問(wèn)題逐步求解。
例子(leetcode-322)：
解題思路：
對(duì)于每個(gè)金額曼追，使用變量j遍歷面值coins數(shù)組
public int CoinChange(int[] coins, int amount)
{
//定義一個(gè)數(shù)組窍仰，數(shù)組下標(biāo)表示金額值(從0到amount),數(shù)據(jù)存放每種金額值所需的最少硬幣個(gè)數(shù)(數(shù)組長(zhǎng)度為amount+1,從0元開(kāi)始)
//例如amount=6,下標(biāo)是: 0, 1, 2, 3, 4, 5, 6 , dp[6]表示下標(biāo)為6元時(shí)所需的最少硬幣個(gè)數(shù)（既dp[i]是最優(yōu)解）
int[] dp = new int[amount + 1] ;
dp[0] = 0;
//數(shù)組1開(kāi)始全部初始化為-1
for (int i = 1; i < dp.Length; i++)
{
dp[i] = -1;
}
//首先遍歷數(shù)組dp,i既表示金額值，從1開(kāi)始
for (int i = 1; i < dp.Length; i++)
{
//其次遍歷面值集合coins
for (int j = 0; j < coins.Length; j++)
{
//dp[i-coins[j]]是重點(diǎn)礼殊，dp[i-coins[j]]表示i金額減去每次遍歷的coins[j]面額驹吮，剩下的取 min{ dp[i-coins[j]] } 最小值
//例如i=6,面值有1，2晶伦，5碟狞，7元，首先遍歷面值為1坝辫，dp[i-coins[j]]表示拿一個(gè)1元出來(lái)篷就，剩下5元，5元最優(yōu)解是dp[5]近忙，是已知的竭业；
//同理，再遍歷2及舍，剩dp[4]未辆；遍歷5，剩dp[1],則求 min{dp[6-1],dp[6-2],dp[6-5]}锯玛，其中最小的值加1就是當(dāng)前金額i的最優(yōu)解
if (i>=coins[j] && dp[i-coins[j]]!= -1 )//找出比i小的面值,且dp[i]的前面dp[比i小的]不能是-1
{
if (dp[i]==-1 || dp[i] > dp[i-coins[j]]+1)
{
dp[i] = dp[i - coins[j]]+1;
}
}
}
}
return dp[amount];
}
總結(jié)：不管子問(wèn)題以后是否被用到咐柜，只要它被計(jì)算過(guò)兼蜈，就將其結(jié)果填入表中(可能之后會(huì)用到子問(wèn)題結(jié)果，這樣就不用再重復(fù)計(jì)算了拙友，降低時(shí)間復(fù)雜度为狸，用空間交換時(shí)間)。這就是動(dòng)態(tài)規(guī)劃法的基本思路遗契。
