目錄

LeetCode 322. 零錢兌換

LeetCode 279. 完全平方數(shù)

LeetCode 139. 單詞拆分

總結

---

LeetCode 322. 零錢兌換

題目鏈接：LeetCode 322. 零錢兌換

思想：首先定義dp數(shù)組的含義，dp[j]即總金額為j的情況下所需的最少的硬幣個數(shù)。接下來確定dp數(shù)組的遞推公式，即在總金額為j的情況下，所需要的硬幣個數(shù)可以是當前值即dp[j]，也可以是減掉當前硬幣面值的前一個dp[j-coins[i]] + 1的值。因為要求最小，所以取他倆的最小值。而關于dp數(shù)組的初始化，因為要求的值是最小值，所以所有的數(shù)都取INT_MAX；其次，dp數(shù)組的所有數(shù)都是根據(jù)dp[0]的值求出的，所以dp[0]要初始化為0，這有什么意義呢，其實也沒啥意義。最后要確定循環(huán)的順序，因為這里只需要找到最少的硬幣個數(shù)，所以組合和排序的順序都可以，其次這里是一個完全背包問題，所以容量要從小到大遍歷。

代碼如下：

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

時間復雜度：O(n^2)，空間復雜度：O(n)。

LeetCode 279. 完全平方數(shù)

題目鏈接：LeetCode 279. 完全平方數(shù)

思想：首先確定dp數(shù)組含義，dp[j]即總和為j的完全平方的最少數(shù)量。dp的遞推公式、初始化和循環(huán)遍歷順序跟上題一樣。本題要注意一點就是在循環(huán)物品的種類的時候，要對n取平方根處理，這樣才好計算完全平方數(shù)。

代碼如下：

    int numSquares(int n) {vector<int> dp(n + 1, INT_MAX);dp[0] = 0;int size = sqrt(n);for (int i = 1; i <= size; i++) {int weight = i * i;for (int j = weight; j <= n; j++) {dp[j] = min(dp[j - weight] + 1, dp[j]);}}return dp[n];}

時間復雜度：O(n^2)，空間復雜度：O(n)。

LeetCode 139. 單詞拆分

題目鏈接：LeetCode 139. 單詞拆分

思想：本題確實沒怎么搞懂，沒把它化解成完全背包問題。遂看題解。首先dp數(shù)組的含義就是，長度為j的字符串是否可以用字典里面的字符串來拼接。遞推公式，如果確定dp[j]是true，且[j,i]在這個區(qū)間的子串出現(xiàn)在字典里，那么dp[i]一定是true。所以遞推公式是 if([j, i] 這個區(qū)間的子串出現(xiàn)在字典里 && dp[j]是true）那么 dp[i] = true。從遞推公式中可以看出，dp[i] 的狀態(tài)依靠 dp[j]是否為true，那么dp[0]就是遞推的根基，dp[0]一定要為true，否則遞推下去后面都都是false了。本題是求拼接成一個字符串，每個字典里的字符串的位置不固定，所以本題應該是排列數(shù)問題，所以先循環(huán)背包，再循環(huán)遍歷物品。

代碼如下：

    bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> wordSet(wordDict.begin(), wordDict.end());vector<bool> dp(s.size() + 1, false);dp[0] = true;for (int i = 1; i <= s.size(); i++) {for (int j = 0; j < i; j++) {string word = s.substr(j, i - j);if (wordSet.find(word) != wordSet.end() && dp[j] == true) {dp[i] = true;}}}return dp[s.size()];}

時間復雜度：O(n^2)，空間復雜度：O(n)。

總結

今天做的昏頭昏腦，還得是要多練習才行。