@ 代码随想录算法训练营第7周(C语言)|Day43(动态规划)
Day41、动态规划(包含题目 ● 1049. 最后一块石头的重量 II ● 494. 目标和 ● 474.一和零 )
1049. 最后一块石头的重量 II
题目描述
有一堆石头,每块石头的重量都是正整数。
每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:
如果 x == y,那么两块石头都会被完全粉碎;
如果 x != y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x。
最后,最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下,就返回 0。
题目解答
int lastStoneWeightII(int* stones, int stonesSize) {
int target;
int sum;
sum=0;
for(int i=0;i<stonesSize;i++){
sum+=stones[i];
}
target=sum/2;
int dp[target+1];
for(int i=0;i<target+1;i++){
dp[i]=0;
}
for(int i=0;i<stonesSize;i++){
for(int j=target;j>=stones[i];j--){
dp[j]=dp[j]>(dp[j-stones[i]]+stones[i])?dp[j]:(dp[j-stones[i]]+stones[i]);
}
}
return sum-dp[target]*2;
}
题目总结
01背包。
494. 目标和
题目描述
给定一个非负整数数组,a1, a2, …, an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数
题目解答
int findTargetSumWays(int* nums, int numsSize, int target) {
int sum=0;
for(int i=0;i<numsSize;i++){
sum+=nums[i];
}
if((sum+target)%2==1){
return 0;
}
if(target<0&&(-target)>sum){
return 0;
}
int k=(sum+target)/2;
int dp[k+1];
for(int i=0;i<=k;i++){
dp[i]=0;
}
dp[0]=1;
for(int i=0;i<numsSize;i++){
for(int j=k;j>=nums[i];j--){
dp[j]+=dp[j-nums[i]];
}
}
return dp[k];
}
题目总结
背包问题。
474.一和零
题目描述
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的大小,该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素,集合 x 是集合 y 的 子集 。### 题目解答
#define MAX(a,b) (a>=b?a:b);
int findMaxForm(char** strs, int strsSize, int m, int n) {
int **dp=(int**)malloc(sizeof(int*)*(m+1));
for(int i=0;i<m+1;i++){
dp[i]=(int*)malloc(sizeof(int)*(n+1));
for(int j=0;j<=n;j++){
dp[i][j]=0;
}
}
for(int z=0;z<strsSize;z++){
int zeronum=0,onenum=0;
for(int h=0;h<strlen(strs[z]);h++){
if(strs[z][h]=='0'){
zeronum++;
}else{
onenum++;
}
}
for(int i=m;i>=zeronum;i--){
for(int j=n;j>=onenum;j--){
dp[i][j]=MAX(dp[i][j],dp[i-zeronum][j-onenum]+1);
}
}
}
return dp[m][n];
}
题目总结
三维01背包。