力扣（494.474）补7.30

494.目标和

关于dp的题我一点都不想提。

看什么时候做题能自己做会吧。一下是力扣大神的解答。

 

 

int findTargetSumWays(int* nums, int numsSize, int target){

    int **dp=malloc(sizeof(int*)*numsSize);

    int sum=0;

    for(int i=0;i

    sum+=nums[i];

    if(fabs(target)>sum)

    return 0;

这个特殊情况也要考虑。

    for(int i=0;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

    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];

 

}