外贸网站谷歌推广,网站建设丿找vx cp5173,网站建设修饰商品,网站积分系统文章目录 ● 完全背包卡码网#xff1a;52. 携带研究材料-完全背包理论练习代码#xff1a; ● 518. 零钱兑换 II思路#xff1a;五部曲 代码#xff1a;滚动数组代码二#xff1a;二维数组 ● 377. 组合总和 Ⅳ思路#xff1a;五部曲 代码#xff1a; ● 完全背包 卡码… 文章目录 ● 完全背包卡码网52. 携带研究材料-完全背包理论练习代码 ● 518. 零钱兑换 II思路五部曲 代码滚动数组代码二二维数组 ● 377. 组合总和 Ⅳ思路五部曲 代码 ● 完全背包 卡码网52. 携带研究材料-完全背包理论练习 代码
import java.util.*;public class Main{public static void main(String[] args){Scanner sc new Scanner(System.in);int Nsc.nextInt();int V sc.nextInt();int[] dpnew int[V1];for(int i0;iN;i){int weightsc.nextInt();int value sc.nextInt();for(int jweight;jV;j){dp[j]Math.max(dp[j],dp[j-weight]value);}}System.out.println(dp[V]);}
}● 518. 零钱兑换 II 思路 五部曲 代码滚动数组
class Solution {public int change(int amount, int[] coins) {// if()return 0;int[] dpnew int[amount1];//初始化dp数组表示金额为0时只有一种情况也就是什么都不装dp[0]1;for(int i0;icoins.length;i){for(int jcoins[i];jamount;j){// dp[j]Math.max(dp[j],dp[j-coins[i]]1);dp[j] dp[j - coins[i]]; //?}}return dp[amount];}
}代码二二维数组
// 二维dp数组版本方便理解
class Solution {public int change(int amount, int[] coins) {int[][] dp new int[coins.length][amount 1];// 只有一种硬币的情况for (int i 0; i amount; i coins[0]) {dp[0][i] 1;}for (int i 1; i coins.length; i) {for (int j 0; j amount; j) {// 第i种硬币使用0~k次求和for (int k 0; k * coins[i] j; k) {dp[i][j] dp[i - 1][j - k * coins[i]];}}}return dp[coins.length - 1][amount];}
}● 377. 组合总和 Ⅳ 思路 五部曲 代码
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];}
}