代码随想录第三十七天(一刷&&C语言)|最后一块石头的重量&&目标和&&一和零

2023-12-22 00:25:07

创作目的:为了方便自己后续复习重点,以及养成写博客的习惯。

一、最后一块石头的重量

思路:参考carl文档

1、确定dp数组以及下标的含义:dp[j]表示容量为j的背包,最多可以背最大重量为dp[j]。石头的重量是 stones[i],石头的价值也是 stones[i] ,可以 最多可以装的价值为 dp[j]?== 最多可以背的重量为dp[j]。

2、确定递推公式:01背包的递推公式为,dp[j] = max(dp[j], dp[j - weight[i]] + value[i])。本题为,dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])。

3、dp数组如何初始化:dp[j]中的j表示容量,最大容量(重量)就是所有石头的重量和。提示中给出1 <= stones.length <= 30,1 <= stones[i] <= 1000,所以最大重量就是30 * 1000 。所求target是最大重量的一半,故dp数组大小为15000。因为重量都不会是负数,所以dp[j]都初始化为0,这样在递归公式dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])中dp[j]才不会初始值所覆盖。

4、确定遍历顺序:使用一维dp数组,物品遍历的for循环放在外层,遍历背包的for循环放在内层,且内层for循环倒序遍历。

5、举例推导dp数组

ledcode题目:https://leetcode.cn/problems/last-stone-weight-ii/description/

AC代码:

#define MAX(a, b) (((a) > (b)) ? (a) : (b))

int getSum(int *stones, int stoneSize) {
    int sum = 0, i;
    for (i = 0; i < stoneSize; ++i)
        sum += stones[i];
    return sum;
}

int lastStoneWeightII(int* stones, int stonesSize){
    int sum = getSum(stones, stonesSize);
    int target = sum / 2;
    int i, j;

    // 初始化dp数组
    int *dp = (int*)malloc(sizeof(int) * (target + 1));
    memset(dp, 0, sizeof(int) * (target + 1));
    for (j = stones[0]; j <= target; ++j)
        dp[j] = stones[0];
    
    // 递推公式:dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])
    for (i = 1; i < stonesSize; ++i) {
        for (j = target; j >= stones[i]; --j)
            dp[j] = MAX(dp[j], dp[j - stones[i]] + stones[i]);
    }
    return sum - dp[target] - dp[target];
}

二、目标和

思路:参考carl文档

1、确定dp数组以及下标的含义:dp[j] 表示填满j(包括j)这么大容积的包,有dp[j]种方法

也可以使用二维dp数组来求解,dp[i][j]表示使用 下标为[0, i]的nums[i]能够凑满j容量的包,有dp[i][j]种方法。

2、确定递推公式:要得到nums[i],凑成dp[j]有dp[j - nums[i]] 种方法。

例:dp[j],j 为5,

已经有一个1(nums[i]) 的话,有 dp[4]种方法 凑成 容量为5的背包。

已经有一个2(nums[i]) 的话,有 dp[3]种方法 凑成 容量为5的背包。

已经有一个3(nums[i]) 的话,有 dp[2]中方法 凑成 容量为5的背包

已经有一个4(nums[i]) 的话,有 dp[1]中方法 凑成 容量为5的背包

已经有一个5 (nums[i])的话,有 dp[0]中方法 凑成 容量为5的背包

那么凑整dp[5]的方法就是把 所有的 dp[j - nums[i]] 累加起来。

递推公式为:dp[j] += dp[j - nums[i]]
3、dp数组如何初始化:从递推公式知,在初始化的时候dp[0] 一定要初始化为1,因为dp[0]是在公式中一切递推结果的起源,如果dp[0]是0的话,递推结果将都是0。dp[j]其他下标对应的数值也应该初始化为0。dp[j]要保证是0的初始值,才能正确的由dp[j - nums[i]]推导出来。

4、确定遍历顺序:对于01背包问题一维dp的遍历,nums放在外循环,target在内循环,且内循环倒序。

5、举例推导dp数组:

输入:nums: [1, 1, 1, 1, 1], S: 3

bagSize = (S + sum) / 2 = (3 + 5) / 2 = 4

lecode题目:https://leetcode.cn/problems/target-sum/description/

AC代码:

int findTargetSumWays(int* nums, int numsSize, int target) {
    int sum = 0;
    for (int i = 0; i < numsSize; i++) {
        sum += nums[i];
    }
    int diff = sum - target;
    if (diff < 0 || diff % 2 != 0) {
        return 0;
    }
    int neg = diff / 2;
    int dp[neg + 1];
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for (int i = 0; i < numsSize; i++) {
        int num = nums[i];
        for (int j = neg; j >= num; j--) {
            dp[j] += dp[j - num];
        }
    }
    return dp[neg];
}

三、一和零

思路:参考carl文档

1、确定dp数组以及下标的含义:dp[i][j]:最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。

2、确定递推公式:dp[i][j] 可以由前一个strs里的字符串推导出来,strs里的字符串有zeroNum个0,oneNum个1。dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。在遍历的过程中,取dp[i][j]的最大值。所以递推公式:dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

3、dp数组如何初始化:01背包的dp数组初始化为0就可以。物品价值不会是负数,初始为0,保证递推的时候dp[i][j]不会被初始值覆盖。

4、确定遍历顺序:01背包为什么一定是外层for循环遍历物品,内层for循环遍历背包容量且从后向前遍历。本题中物品就是strs里的字符串,背包容量就是题目描述中的m和n。

5、举例推导dp数组。

ledcode题目:https://leetcode.cn/problems/ones-and-zeroes/description/

AC代码:

void getZerosOnes(int* zerosOnes, char* str) {
    int length = strlen(str);
    for (int i = 0; i < length; i++) {
        zerosOnes[str[i] - '0']++;
    }
}

int findMaxForm(char** strs, int strsSize, int m, int n) {
    int length = strsSize;
    int dp[m + 1][n + 1];
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < length; i++) {
        int zerosOnes[2];
        memset(zerosOnes, 0, sizeof(zerosOnes));
        getZerosOnes(zerosOnes, strs[i]);
        int zeros = zerosOnes[0], ones = zerosOnes[1];
        for (int j = m; j >= zeros; j--) {
            for (int k = n; k >= ones; k--) {
                dp[j][k] = fmax(dp[j][k], dp[j - zeros][k - ones] + 1);
            }
        }
    }
    return dp[m][n];
}

文章来源:https://blog.csdn.net/qq_57729144/article/details/135141592
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。