題目：322.零錢兌換

嘗試解答：

1.確定dp[j]含義：裝滿容量為j的背包所需要放的硬幣個數為dp[j];

2.動態轉移方程：dp[j] = dp[j - coins[i]] + 1;

3.遍歷順序：本題應該為組合類題目，不考慮裝入的順序，只在乎硬幣個數

? ? ? ? 所以先物品后背包，背包容量從小到大。（錯）

4.初始化：dp[0] = 1,其余均初始換為0

5.打印dp

代碼實現如下，有漏洞，執行不對：

class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount + 1, 0);dp[0] = 1;int result = INT_MAX;for(int i = 0; i < coins.size(); i++){for(int j = coins[i]; j <= amount; j++){// dp[j] = dp[j - coins[i]] + 1;// result = min(dp[j], result);if(j == amount){result = min(dp[j], result);}}}return result;}
};

正確思路：

1.確定dp[j]含義：裝滿容量為j的背包所需要最少放的硬幣個數為dp[j];

2.動態轉移方程：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

? ? ? ? 本輪要放的物品重量為coins[i]，所以背包必須騰出coins[i]這么大的容量留給coins[i]，所以之前背包裝的重量必須是dp[j - coins[i]]。裝了coins[i]后，一共裝了dp[j - coins[i]] + 1塊硬幣，與不裝coins[i] 的情況比大小，取其小，得到本輪循環的最優解，就是本次的最少個數。

3.初始化：

????????本題初始化比較取巧，之前不管是排列還是組合，dp[0]都初始化為了1，但這到題從測試樣例中可以看出，dp[0] = 0。

? ? ? ? 其他位置的值如何進行初始化？從本質入手，因為是取其小，必須將他們初始化為INT_MAX，才可以保證在二維數組的第一行可以成功更改值，不會被原來初始化的值覆蓋（解釋這一點時我習慣從二維數組的角度出發）。

? ? ? ? 其實道理和其他題目中，初始化為0的道理是一樣的，其他題目如果是取其大max，則初始化為0，只要沒有負數的情況，就可以保證能夠更新值，不會被覆蓋。

4.遍歷順序：

? ? ? ? 本題對遍歷順序無要求。

? ? ? ? 首先要分清楚題目類型：本題是求裝滿背包的最少個數，不是求裝滿背包有多少種方法，

所以這道題和排列組合無關，對遍歷順序無特殊要求。

? ? ? ? 只有題目問“方法數”時，才考慮排列還是組合，先背包還是先物品。

5.打印dp

代碼如下：

class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount + 1, INT_MAX);dp[0] = 0;for(int i = 0; i < coins.size(); i++){      //遍歷物品for(int j = coins[i]; j <= amount; j++){     //遍歷背包if(dp[j - coins[i]] != INT_MAX){dp[j] = min(dp[j - coins[i]] + 1, dp[j]);}}}if(dp[amount] == INT_MAX) return -1;return dp[amount];}
};

對于返回-1的條件不是很理解。

循環里的判斷條件：如果dp[j - coins[i]] != INT_MAX，那么是不可能通過目前遍歷到的物品將背包裝滿的。

返回值時進行的判斷：如果dp[amount] == INT_MAX，那么不可能將背包裝滿。