@ 代码随想录算法训练营第7周（C语言）|Day43（动态规划）

@ 代码随想录算法训练营第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背包。