大学毕业网站设计代做,wordpress作者函数,石家庄网站建设设计,网络公关名词解释完全背包
完全背包的每件商品都有无限个#xff0c;和01背包的一不同主要体现在遍历顺序上。为了保证每个物品仅被添加一次#xff0c;01背包内嵌的循环是从大到小遍历。而完全背包的物品是可以添加多次的#xff0c;所以要从小到大去遍历。
518. 零钱兑换 II
思路#…完全背包
完全背包的每件商品都有无限个和01背包的一不同主要体现在遍历顺序上。为了保证每个物品仅被添加一次01背包内嵌的循环是从大到小遍历。而完全背包的物品是可以添加多次的所以要从小到大去遍历。
518. 零钱兑换 II
思路每一种面额的硬币有无限个是完全背包问题。背包的容量为amount物品的重量和价值都是硬笔金额。求组合数 dp[j]表示容量为j时成立的组合数。
代码如下
class Solution {public int change(int amount, int[] coins) {int[] dpnew int[amount1];dp[0]1;for(int i0;icoins.length;i){for(int jcoins[i];jamount;j){dp[j]dp[j-coins[i]];}}return dp[amount];}
}377. 组合总和 Ⅳ
思路本题与上一题的区别在于本题是求排列的个数。
如果求组合数就是外层for循环遍历物品内层for遍历背包。 如果求排列数就是外层for遍历背包内层for循环遍历物品。
代码如下
class Solution {public int combinationSum4(int[] nums, int target) {int[] dpnew int[target1];dp[0]1;for(int j0;jtarget;j){for(int i0;inums.length;i){if(jnums[i]){dp[j]dp[j-nums[i]];}}}return dp[target];}
}70. 爬楼梯 进阶
思路dp[i]指爬到有i个台阶的楼顶有dp[i]种方法。台阶可以重复使用-完全背包问题从前往后遍历背包。求排列的个数背包是外层循环。
代码如下
import java.util.Scanner;
class Main{public static void main(String [] args){Scanner scannew Scanner(System.in);int m,n;while (scan.hasNextInt()) {nscan.nextInt();mscan.nextInt();int[] dpnew int[n1];dp[0]1;for(int j1;jn;j){for(int i1;im;i){if(ji) dp[j]dp[j-i];}}System.out.println(dp[n]);}}
}
