完全背包

有N件物品和一个容量为W的背包，第 i 件物品的重量是weight[ i ]，价值为value[ i ]，每件物品都有无限个，求解使用背包物品价值总和达到最大的装包方案  

二维

static int CompleteKnapsack2D(int[] weights, int[] values, int W)
{int n = weights.Length;int[,] dp = new int[n + 1, W + 1];// 遍历每个物品for (int i = 1; i <= n; i++){for (int j = 0; j <= W; j++){// 如果不使用当前物品dp[i, j] = dp[i - 1, j];// 如果使用当前物品if (j >= weights[i - 1]){dp[i, j] = Math.Max(dp[i, j], dp[i, j - weights[i - 1]] + values[i - 1]);}}}return dp[n, W];
}

一维

static int CompleteKnapsack1D(int[] weights, int[] values, int W)
{int n = weights.Length;int[] dp = new int[W + 1];// 遍历所有的物品for (int i = 0; i < n; i++){// 遍历背包容量从小到大for (int j = weights[i]; j <= W; j++){// 更新 dp 数组dp[j] = Math.Max(dp[j], dp[j - weights[i]] + values[i]);}}return dp[W];
}

summary

518. 零钱兑换Ⅱ

题目：518. 零钱兑换 II - 力扣（LeetCode）
题解：代码随想录 (programmercarl.com)
比较简单

solution

public class Solution {public int Change(int amount, int[] coins) {int[] dp = new int[amount + 1];dp[0] = 1;for(int i = 0; i < coins.Length; i ++){for(int j = coins[i]; j <= amount; j ++){dp[j] = dp[j] + dp[j - coins[i]];}}return dp[amount];}
}

summary

注意dp[0]需要初始化为1

377. 组合总和Ⅳ

题目：377. 组合总和 Ⅳ - 力扣（LeetCode）
题解：代码随想录 (programmercarl.com)
想不通，明天再想

solution

public class Solution {public int CombinationSum4(int[] nums, int target) {// 创建 dp 数组，大小为 target + 1int[] dp = new int[target + 1];dp[0] = 1; // 组成 0 的组合数量为 1（空组合）// 遍历所有目标数值for (int i = 1; i <= target; i++){// 遍历所有候选数字foreach (int num in nums){if (i >= num){// 更新 dp[i] 的值dp[i] += dp[i - num];}}}// 返回组成 target 的组合数量return dp[target];}
}

summary