网站js特效,免费网页小游戏,制作网站时搜索图标如何做,企业网站托管外包方案一、完全背包
卡哥的总结#xff0c;还挺全代码随想录 (programmercarl.com) 二、零钱兑换 II 518. 零钱兑换 II - 力扣#xff08;LeetCode#xff09; 被选物品之间不需要满足特定关系#xff0c;只需要选择物品#xff0c;以达到「全局最优」或者「特定状态」即可。 …一、完全背包
卡哥的总结还挺全代码随想录 (programmercarl.com) 二、零钱兑换 II 518. 零钱兑换 II - 力扣LeetCode 被选物品之间不需要满足特定关系只需要选择物品以达到「全局最优」或者「特定状态」即可。 同时硬币相当于我们的物品每种硬币可以选择「无限次」很自然的想到「完全背包」。 这时候可以将「完全背包」的状态定义搬过来进行“微调” 定义 f[i][j]为考虑前 iii 件物品凑成总和为 jjj 的方案数量。 为了方便初始化我们一般让 f[0][x] 代表不考虑任何物品的情况。 因此我们有显而易见的初始化条件f[0][0]1其余 f[0][x]0。 代表当没有任何硬币的时候存在凑成总和为 0 的方案数量为 1凑成其他总和的方案不存在。 当「状态定义」与「基本初始化」有了之后我们不失一般性的考虑 f[i][j] 该如何转移。 对于第 i 个硬币我们有两种决策方案 不使用该硬币 f[i−1][j] 使用该硬币由于每个硬币可以被选择多次容量允许的情况下因此方案数量应当是选择「任意个」该硬币的方案总和 class Solution {public int change(int cnt, int[] cs) {int n cs.length;int[][] f new int[n 1][cnt 1];f[0][0] 1;for (int i 1; i n; i) {int val cs[i - 1];for (int j 0; j cnt; j) {f[i][j] f[i - 1][j];for (int k 1; k * val j; k) {f[i][j] f[i - 1][j - k * val]; }}}return f[n][cnt];}
} 三、组合总和 Ⅳ 377. 组合总和 Ⅳ - 力扣LeetCode emmmmm看官方题解吧377. 组合总和 Ⅳ - 力扣LeetCode
