22号就要复试了,专业课,英语都还没搞,我的吗,先每天刷10道旧题在刷新题把。

int max(int i,int j){
    if(i>j) return i;
    return j;
}

bool canPartition(int* nums, int numsSize) {
    int sum=0;
    for(int i=0;i<numsSize;i++){
        sum+=nums[i];
    }
    if(sum%2!=0) return false;
    int size=sum/2;
    int** dp=(int**)malloc(sizeof(int*)*numsSize);
    for(int i=0;i<numsSize;i++) dp[i]=(int*)malloc(sizeof(int)*(size+1));
    for(int i=0;i<numsSize;i++) dp[i][0]=0;
    for(int i=nums[0];i<=size;i++) dp[0][i]=nums[0];
    for(int i=1;i<numsSize;i++){
        for(int j=1;j<=size;j++){
            if(nums[i]>j){
                dp[i][j]=dp[i-1][j];
            }else{
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i]);
            }
            if(dp[i][j]==sum/2) return true;
        }
    }    
    return false;
}

结果:

声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。