完全背包

感覺越寫越糊涂了，初始化怎么做的？遞推公式怎么來的？

卡碼52. 攜帶研究材料

https://kamacoder.com/problempage.php?pid=1052

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt(); //研究材料的種類int bagSize = sc.nextInt(); //行李空間 int[] weight = new int[N];int[] value = new int[N];for(int i=0; i<N; i++) {weight[i] = sc.nextInt();value[i] = sc.nextInt();}int[]dp = new int[bagSize+1];for(int i=0; i<N; i++) {for(int j=weight[i]; j<bagSize+1; j++) {dp[j] = Math.max(dp[j], dp[j-weight[i]] + value[i]);}}System.out.println(dp[bagSize]);}
}

518. 零錢兌換 II

這道題使用動態規劃：當前狀態依靠上一狀態得到。

• 初始化出錯：dp[0]=1的意思是，amount等于0的時候 湊成總金額0的貨幣組合數為1

class Solution {public int change(int amount, int[] coins) {int[]dp = new int[amount+1];dp[0] = 1;//dp[j]: 總金額為j的時候，有dp[j]種方式找零錢//int M = coins.length;for(int i=0; i<M; i++) {for(int j=coins[i]; j<= amount; j++) {dp[j] = dp[j] += dp[j-coins[i]];}}return dp[amount];}
}

• 別人的二維數組解法

class Solution {public int change(int amount, int[] coins) {int n = coins.length;int[][] f = new int[n + 1][amount + 1];f[0][0] = 1;for (int i = 0; i < n; i++) {for (int c = 0; c <= amount; c++) {if (c < coins[i]) {f[i + 1][c] = f[i][c];} else {f[i + 1][c] = f[i][c] + f[i + 1][c - coins[i]];}}}return f[n][amount];}
}

377. 組合總和 Ⅳ

和518. 零錢兌換 II 的區別：① 求組合(518)先物品后背包 ② 求排列(377)先背包后物品

先物品后背包：先把物品0放進來，然后把物品1放進來，所以我們計算的情況順序只有（物品0，物品1）的情況，不會出現（物品1，物品0），因此為組合

class Solution {public int combinationSum4(int[] nums, int target) {int[]dp = new int[target+1];//初始化dp[0] = 1;//遞推//dp[i][j]表示 從物品0-i任取，滿足恰好等于 j ,所有可能的組合有dp[i][j]個for(int i=0; i<=target; i++) {for(int j=0; j<nums.length; j++){if (i >= nums[j]) {dp[i] += dp[i - nums[j]];}}}return dp[target];}
}// 完全背包的初始化不太一樣
// 0-1背包對首行（當weight[0]<=j的時候，dp[0][j]=value[i]）首列進行初始化

70. 爬樓梯 （進階）

• 錯誤：for i=1 for j=1
• 而且 j<=M ，包含等于

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int bagSize = sc.nextInt();int M = sc.nextInt();int[] dp = new int [bagSize+1];dp[0] = 1;for(int i=1; i<bagSize+1; i++) {for(int j=1; j<=M; j++) { //物品if(i >= j) {dp[i] += dp[i-j]; }}}System.out.println(dp[bagSize]);}
}