494.目标和
关于dp的题我一点都不想提。
看什么时候做题能自己做会吧。一下是力扣大神的解答。
int findTargetSumWays(int* nums, int numsSize, int target){
int **dp=malloc(sizeof(int*)*numsSize);
int sum=0;
for(int i=0;i<numsSize;i++)
sum+=nums[i];
if(fabs(target)>sum)
return 0;
这个特殊情况也要考虑。
for(int i=0;i<numsSize;i++){
dp[i]=malloc(sizeof(int)*(sum*2+1));
memset(dp[i],0,sizeof(int)*(sum*2+1));
}
if(nums[0]==0)
dp[0][sum]=2;
else{
dp[0][sum+nums[0]]=1;
dp[0][sum-nums[0]]=1;}
这里的初始化也很重要，难想到。
for(int i=1;i<numsSize;i++){
for(int j=0;j<=2*sum;j++){
int l=(j-nums[i])>=0?j-nums[i]:0;
int r=(j+nums[i])<=2*sum?j+nums[i]:0;
这里是考虑j+–nums（i）的问题会不会超过列的长度，超过则设为0，因为dp（i–1）（0）为0。看表格就知道由dp（i）（j）由左上j+nums（i）和右上j-nums（i）构成。
dp[i][j]=dp[i-1][l]+dp[i-1][r];
}
}
return dp[numsSize-1][sum+target];
这里下标不是target，容易出错。
}
474.一零和
这题先要理解题意，对0，1数量的要求是针对整个二维字符串数组的，不是二维数组的某个元素。
dp（i）（j）表示含最多m个0和n个1的最大子集的个数，这里所有的子集结果应是三维数组，三维数组中选择元素最多的二维数组。
动态规划的循环还是有细节的。要注意。还是那句话，要跟着用例推一遍。
但这种三维数组不好推。只能往二维数组的思路去靠。
抱歉，我实在不能深刻理解dp，只能这样想了：
如果当前字符串加不了，则为dp（i-1）（j）（k），
如果能加，考虑不加与加的情况，取更大值。
这样说，我才能觉得做题有一点点的思路。
int findMaxForm(char ** strs, int strsSize, int m, int n){
int dp[strsSize+1][m+1][n+1];
memset(dp,0,sizeof(dp));
for(int k1=1;k1<=strsSize;k1++){
int zeronum=0;
int onenum=0;
for(int k=0;strs[k1-1][k];k++){
if(strs[k1-1][k]=='0')
zeronum++;
else
onenum++;
}
for(int i=0;i<=m;i++){
for(int j=0;j<=n;j++){
dp[k1][i][j]=dp[k1-1][i][j];
if(i>=zeronum&&j>=onenum)
dp[k1][i][j]=fmax(dp[k1-1][i][j],dp[k1-1][i-zeronum][j-onenum]+1);
}}
}
return dp[strsSize][m][n];
}