视频讲解：https://www.bilibili.com/video/BV1uK411o7c9

https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85.html 

思路

#include <stdio.h>
#include <stdlib.h>
int max_value(int N, int V, int items[][2]) {
    int *dp = (int *)malloc((V + 1) * sizeof(int));
    for (int i = 0; i <= V; i++) {
        dp[i] = 0;
    }
    for (int i = 0; i < N; i++) {
        int wi = items[i][0]; 
        int vi = items[i][1]; 
        for (int j = wi; j <= V; j++) {
            if (dp[j] < dp[j - wi] + vi) {
                dp[j] = dp[j - wi] + vi;
            }
        }
    }
    int result = dp[V]; 
    free(dp); 
    return result;
}

int main() {
    int N, V;
    scanf("%d %d", &N, &V);
    int (*items)[2] = malloc(N * sizeof(*items));
    for (int i = 0; i < N; i++) {
        scanf("%d %d", &items[i][0], &items[i][1]);
    }
    int result = max_value(N, V, items);
    printf("%d\n", result);  
    free(items); 
    return 0;
}

学习反思

包问题是指有一定容量的背包和一组物品，每个物品有自己的重量和价值，目标是找到一个组合，使得背包能够容纳的情况下，所装物品的总价值最大。代码中的max_value函数实现了动态规划的逻辑，其中N表示物品的个数，V表示背包的容量，items是一个二维数组，存储了每个物品的重量和价值。首先，通过动态分配内存，创建了一个大小为V+1的一维数组dp，用来保存每种容量下的背包的最大价值。初始化dp数组的所有元素为0。然后，遍历物品数组，对于每个物品，通过两层循环，从背包容量wi开始，到背包容量V，逐渐增加容量，计算当前容量下背包的最大价值。具体计算方式是，如果背包的当前容量j大于等于当前物品的重量wi，那么将当前物品的价值vi加上dp[j-wi]的值，与dp[j]比较，取较大的值更新dp[j]。最后，返回dp[V]，即背包容量为V时的最大价值。在主函数中，首先读取输入的N和V，然后动态分配内存，创建一个二维数组items，用来保存每个物品的重量和价值。然后，通过循环遍历，逐个读取每个物品的重量和价值，并保存到items数组中。接着，调用max_value函数，传入N、V和items，得到背包容量为V时的最大价值，将结果保存到result变量中。最后，输出result的值，并释放items数组占用的内存。

518. 零钱兑换 II

视频讲解：https://www.bilibili.com/video/BV1KM411k75j

https://programmercarl.com/0518.%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2II.html

思路

int change(int amount, int* coins, int coinsSize) {
    int dp[amount + 1];
    memset(dp, 0, sizeof (dp));
    dp[0] = 1;
    for(int i = 0; i < coinsSize; i++){
        for(int j = coins[i]; j <= amount; j++){
            dp[j] += dp[j - coins[i]];
        }
    }
    return dp[amount];
}

学习反思

代码中的change函数实现了动态规划的逻辑，其中amount表示需要凑成的金额，coins是一个整数数组，存储了不同面额的硬币。首先，创建一个大小为amount+1的整数数组dp，用来保存每种金额下所需的最少硬币数量。使用memset函数将dp数组初始化为0。然后，将dp[0]设置为1，表示凑成金额为0的情况只有一种，即不选取任何硬币。接下来，通过两层循环，遍历硬币数组。对于每个硬币coins[i]，从硬币的面额coins[i]开始，逐渐增加金额，计算当前金额下的最少硬币数量。具体计算方式是，将dp[j-coins[i]]的值加到dp[j]上，表示当前金额j可以由dp[j-coins[i]]种硬币的基础上再加上一枚面额为coins[i]的硬币得到。最后，返回dp[amount]，即凑成金额amount所需的最少硬币数量。

377. 组合总和 Ⅳ

视频讲解：https://www.bilibili.com/video/BV1V14y1n7B6

https://programmercarl.com/0377.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C%E2%85%A3.html

思路

int combinationSum4(int* nums, int numsSize, int target) {
    int dp[target + 1];
    memset(dp, 0, sizeof (dp ));
    dp[0] = 1;
    for(int i = 0; i <= target; i++){
        for(int j = 0; j < numsSize; j++){
            if(i - nums[j] >= 0 && dp[i] < INT_MAX - dp[i - nums[j]]){
                dp[i] += dp[i - nums[j]];
            }
        }
    }
    return dp[target];
}

学习反思

combinationSum4函数实现了动态规划的逻辑，其中nums是一个整数数组，numsSize表示数组的大小，target是目标值。首先，创建一个大小为target+1的整数数组dp，用来保存每个目标值下的组合个数。使用memset函数将dp数组初始化为0。然后，将dp[0]设置为1，表示和为0的情况有一种，即不选取任何元素。接下来，通过两层循环，遍历目标值和数组元素。对于每个目标值i和每个数组元素nums[j]，判断如果i减去nums[j]大于等于0，并且组合数量dp[i]加上dp[i - nums[j]]不会溢出，则将dp[i]加上dp[i - nums[j]]。这个操作表示，当前目标值i可以由dp[i-nums[j]]种组合的基础上再加上一种选择元素nums[j]得到。最后，返回dp[target]，即由nums中的元素组成，和为target的组合的个数。

70. 爬楼梯 （进阶）

https://programmercarl.com/0070.%E7%88%AC%E6%A5%BC%E6%A2%AF%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85%E7%89%88%E6%9C%AC.html

思路

#include <stdio.h>
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    int dp[n + 1];
    dp[0] = 1; 
    dp[1] = 1; 
    for (int i = 2; i <= n; i++) {
        dp[i] = 0; // Reset dp[i]
        for (int j = 1; j <= m && j <= i; j++) {
            dp[i] += dp[i - j]; 
        }
    }
    printf("%d\n", dp[n]);
    
    return 0;
}

学习反思

首先通过scanf函数获取输入的整数n和整数m。然后，创建一个大小为n+1的整数数组dp，用来保存拆分成m个整数的和的方式数量。并将dp[0]和dp[1]设置为1，即将n拆分成0个整数或者1个整数的方式数量都为1。接下来，通过两层循环进行动态规划的计算。外层循环遍历从2到n的每一个整数i，内层循环遍历从1到m的每一个整数j，并且j不能大于i。在每次外层循环中，先将dp[i]重置为0，然后将dp[i]加上dp[i-j]，表示将整数i拆分成m个整数的和，其中最后一个整数为j。最后，输出dp[n]，即将整数n拆分成m个整数的和的方式数量。

总结

加油！！！！