1049. 最后一块石头的重量 II
视频讲解：https://www.bilibili.com/video/BV14M411C7oV
https://programmercarl.com/1049.%E6%9C%80%E5%90%8E%E4%B8%80%E5%9D%97%E7%9F%B3%E5%A4%B4%E7%9A%84%E9%87%8D%E9%87%8FII.html
思路
#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;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];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];
}学习反思
实现了解决最后一块石头的重量问题。代码的主要思路是使用动态规划来计算最大重量的一半，然后用总重量减去最大重量的一半的两倍。首先，定义了一个宏函数MAX，用来取两个数中的最大值。接下来，定义了一个函数getSum，用来计算数组stones中所有元素的和。然后，在lastStoneWeightII函数中，首先计算了数组stones的总和sum，并计算了最大重量的一半target。接下来，使用动态规划的思想，创建了一个大小为target+1的dp数组，并将其初始化为0。然后，从数组stones的第一个元素开始，遍历数组stones，对于每个元素，从target向stones[i]遍历dp数组，并更新dp[j]的值为当前元素stones[i]的重量和dp[j-stones[i]]的值之和的最大值。最后，返回sum - dp[target] - dp[target]，即总重量减去最大重量的一半的两倍。时间复杂度为O(stonesSize * target)，空间复杂度为O(target)。
494. 目标和
视频讲解：https://www.bilibili.com/video/BV1o8411j73x
https://programmercarl.com/0494.%E7%9B%AE%E6%A0%87%E5%92%8C.html
思路
int getSum(int * nums, int numsSize){int sum = 0;for(int i = 0; i < numsSize; i++){sum += nums[i];}return sum;
}
int findTargetSumWays(int* nums, int numsSize, int target) {int sum = getSum(nums, numsSize);int diff = sum - target;if(diff < 0 || diff % 2 != 0){return 0;}int bagSize = diff / 2;int dp[numsSize + 1][bagSize + 1];dp[0][0] = 1;for(int i = 1; i <= numsSize; i++){int num = nums[i - 1];for(int j = 0; j <= bagSize; j++){dp[i][j] = dp[i - 1][j];if(j >= num){dp[i][j] += dp[i - 1][j - num];}}}return dp[numsSize][bagSize];
}学习反思
实现了解决目标和问题。目标和问题是给定一个非负整数数组和一个目标整数，要求从数组中选择一些元素，使得它们的和等于目标整数。这段代码使用动态规划的思想来解决该问题。首先，定义了一个函数getSum，用来计算数组nums中所有元素的和。然后，在findTargetSumWays函数中，首先计算了数组nums的总和sum，并计算了数组元素和目标整数之差diff。如果diff小于0或diff不是偶数，即无法找到满足条件的解，返回0。接下来，计算容量为diff / 2的背包的最大容量bagSize。然后，创建了一个大小为numsSize + 1行、bagSize + 1列的dp数组，并将dp[0][0]初始化为1，表示当没有元素和背包容量为0时，有一种选择方式。然后，使用二维动态规划的思想，遍历数组nums，并在每个位置(i, j)上计算选择前i个元素，使得和为j的方案数。对于当前位置(i, j)，如果当前元素nums[i-1]小于等于背包容量j，意味着可以选择当前元素，那么dp[i][j]的值为上一行的dp[i-1][j]加上上一行的dp[i-1][j-nums[i-1]]（即选择当前元素后背包容量减少了nums[i-1]）的值。最后，返回dp[numsSize][bagSize]，即选择前numsSize个元素，使得和为bagSize的方案数。时间复杂度为O(numsSize * bagSize)，空间复杂度为O(numsSize * bagSize)。
474.一和零
视频讲解：https://www.bilibili.com/video/BV1rW4y1x7ZQ
https://programmercarl.com/0474.%E4%B8%80%E5%92%8C%E9%9B%B6.html
思路
#define max(a, b) ((a) > (b) ? (a) : (b))
int findMaxForm(char** strs, int strsSize, int m, int n) {int dp[m + 1][n + 1];memset(dp, 0, sizeof (int ) * (m + 1) * (n + 1));for(int i = 0; i < strsSize; i++){// 统计0和1的数量int count0 = 0;int count1 = 0;char *str = strs[i];while (*str != '\0'){if(*str == '0'){count0++;} else{count1++;}str++;}for(int j = m; j >= count0; j--){for(int k = n; k >= count1; k--){dp[j][k] = max(dp[j][k], dp[j - count0][k - count1] + 1);}}}return dp[m][n];
}学习反思
实现了解决0-1背包问题的一种变种，即找到最大能够由给定字符串数组中的元素组成的字符串数量，其中每个字符串的0和1的数量不超过给定的m和n。首先，定义了一个宏函数max用来取两个数的最大值。然后，在findMaxForm函数中，创建了一个大小为(m + 1) * (n + 1)的二维数组dp，并将其初始化为0。接下来，对于给定的字符串数组中的每个字符串，统计其0和1的数量。然后，使用二维动态规划的思想，从m和n开始递减遍历，表示剩余的0和1的数量。对于当前剩余的0和1的数量(j, k)，dp[j][k]表示能够由前i个字符串组成的字符串数量。如果当前字符串的0和1的数量(count0, count1)小于等于剩余的0和1的数量(j, k)，则表示可以选择当前字符串，那么dp[j][k]的值为上一行的dp[j][k]和上一行的dp[j - count0][k - count1] + 1（即选择当前字符串后剩余的0和1的数量减少了count0和count1）的最大值。最后，返回dp[m][n]，即能够由给定字符串数组中的元素组成的最大字符串数量。时间复杂度为O(strsSize * m * n)，空间复杂度为O(m * n)。
总结
动态规划，加油！！！
