力扣題目：#518.零錢兌換II（完全背包組合問題）
刷題時(shí)長：7min
解題方法：動(dòng)態(tài)規(guī)劃（完全背包）
復(fù)雜度分析
- 時(shí)間復(fù)雜度: O(mn)，其中 m 是amount，n 是 coins 的長度
- 空間復(fù)雜度: O(m)
問題總結(jié)文章來源：http://www.zghlxwxcb.cn/news/detail-535869.html
- 對(duì)遞推公式的理解
本題收獲文章來源地址http://www.zghlxwxcb.cn/news/detail-535869.html
- 題意轉(zhuǎn)換：純完全背包是湊成背包最大價(jià)值是多少，而本題是要求湊成總金額的物品組合個(gè)數(shù)
- 動(dòng)規(guī)思路
- 確定dp數(shù)組及下標(biāo)的含義：湊成總金額j的貨幣組合數(shù)為dp[j]
- 確定遞推公式：dp[j] += dp[j - coins[i]]
- 反向思考遞推，當(dāng)有coins[i]時(shí)，就有dp[j-coins]種方法，因?yàn)榇藭r(shí)湊成目標(biāo)和的方法解即為j+coins[i]，而方法數(shù)量不變
- dp數(shù)組的初始化：dp[0] = 1
- 確定遍歷順序：求組合，遍歷必須先物品(coins)，再背包(amount)
力扣題目：#377.組合總和Ⅳ（完全背包排列問題）
刷題時(shí)長：7min
解題方法：動(dòng)態(tài)規(guī)劃（完全背包）
復(fù)雜度分析
- 時(shí)間復(fù)雜度: O(target * n)，其中 n 為 nums 的長度
- 空間復(fù)雜度: O(target)
問題總結(jié)
- 題目要求的combination其實(shí)是排列數(shù)，需要仔細(xì)看sample
- 先背包的遍歷順序需要加條件判斷，先物品再背包不需要是因?yàn)閷懺谘h(huán)index的邊界值里了
本題收獲
- 動(dòng)規(guī)思路
- 確定dp數(shù)組及下標(biāo)的含義：湊成目標(biāo)正整數(shù)為i的排列個(gè)數(shù)為dp[i]
- 確定遞推公式：dp[i] += dp[i - nums[j]]
- dp數(shù)組的初始化：dp[0] = 1
- 確定遍歷順序：求排列數(shù)就是外層for遍歷背包，內(nèi)層for循環(huán)遍歷物品
到了這里，關(guān)于力扣算法刷題Day44｜動(dòng)態(tài)規(guī)劃：完全背包問題 零錢兌換II 組合總和Ⅳ的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
