今天的幾道題目都比較簡單,思路也比較相似,都是利用完全背包。完全背包和01背包的不同點在于完全背包每個元素可以取多次,而01背包只能取1次,所以在dp一維數組遍歷時,完全背包仍然要從前往后遍歷,并且無論是先遍歷物品還是先遍歷背包都可以,但是先遍歷物品和先遍歷背包在次數上是有差別的,只是在求最大價值時得到的結果相同。先遍歷物品時,一定是前面的物品遍歷完之后再遍歷后面的物品,所以這是組合;在先遍歷背包時,是用一個背包容量將所有物品掃過一遍后才查找下一個背包容量,所以滿足要求的填滿背包的物品有不同的順序,所以這是排列
完全背包
視頻講解:
https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85.html
518. 零錢兌換 II
視頻講解:
https://programmercarl.com/0518.%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2II.html
377. 組合總和 Ⅳ
視頻講解:代碼隨想錄
70. 爬樓梯 (進階)
這道題目 爬樓梯之前我們做過,這次再用完全背包的思路來分析一遍
https://programmercarl.com/0070.%E7%88%AC%E6%A5%BC%E6%A2%AF%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85%E7%89%88%E6%9C%AC.html