518. 零钱兑换 II
文档和视频讲解:代码随想录(programmercarl.com)
状态:ac
用时:1h
思路:
最重要的是完全背包的遍历顺序,组合和排序的遍历顺序需要注意:如果求组合数就是外层for循环遍历物品,内层for遍历背包。
如果求排列数就是外层for遍历背包,内层for循环遍历物品。
代码:
377. 组合总和 Ⅳ
文档和视频讲解:代码随想录(programmercarl.com)
状态:ac
用时:1h
思路:
该题计算排列个数,还是要注意遍历顺序:如果求组合数就是外层for循环遍历物品,内层for遍历背包。如果求排列数就是外层for遍历背包,内层for循环遍历物品。
代码:
注:该题给的C++测试用例有两个数相加超过int的数据,所以需要在if里加上dp[i] < INT_MAX - dp[i - num]。