8.11 周五

• ?70.?爬樓梯?（進階）

• ?322.?零錢兌換?

• ?279.完全平方數?

?詳細布置?

?70.?爬樓梯?（進階）?

題目：一次可爬1或2個臺階，問n個臺階有多少種方式

題解：

1、轉換為完全背包問題，nums=[1,2],target是n

2、背包從前往后遍歷（完全背包）

3、先遍歷背包，再遍歷物品（與物品順序有關）

3、dp[0]=1

?322.?零錢兌換??

題目：

給定不同面額的硬幣 coins 和一個總金額 amount。計算可以湊成總金額所需的最少的硬幣個數。

題解：

1、將dp[i]用Integer.MAX_VALUE填充

2、物品從前往后（完全背包）

3、物品和背包這兩層for循環可交換位置（因為與物品順序無關）

4、dp[0]=0

5、每次要判斷dp[j-coint[i]]，因為是從前往后遍歷，必須要之前的值有更新才沿著之前的繼續

if (dp[j - coins[i]] != INT_MAX) { // 如果dp[j - coins[i]]是初始值則跳過

?279.完全平方數??

題目：用完全平方數湊成n，問組合的最少元素個數

題解：

1、dp[]初始化為max_value

2、dp[0]=0因為物品從1開始

3、每次判斷dp[j-i*i]的值是不是max_value，是的話說明這個值還沒更新過，不能繼續下去。

4、背包從前往后（完全背包）

5、背包和物品循環位置可交換（最少個數）

總結

如果求組合數就是外層for循環遍歷物品，內層for遍歷背包。（與物品順序無關，所以保持一種順序）

如果求排列數就是外層for遍歷背包，內層for循環遍歷物品。（與物品順序有關，所以有多個順序）

如果求組合最小個數就是兩層for循環可交換位置。（與物品順序有關還是無關，都不影響組合內的元素個數）

?