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

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

一、最后一块石头的重量

思路：参考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];
}