Leetcode 1049. 最后一块石头的重量 II(DAY 39) ---

发布于:2021-09-18 09:08:59

原题题目




代码实现(首刷自解)

int cmp(const void* a,const void* b)
{
return *(int*)a - *(int*)b;
}

int lastStoneWeightII(int* stones, int stonesSize){
int i,j,sum = 0,min = INT_MAX-1;
for(i=0;i sum += stones[i];
int scale = sum/2+1;
int dp[31][10000];
qsort(stones,stonesSize,sizeof(int),cmp);
for(i=0;i {
for(j=1;j<=scale;j++)
{
if(j == stones[i] || (i>=1 && dp[i-1][j]))
{
dp[i][j] = 1;
if(fabs(sum - j - j) < min) min = fabs(sum - j - j);
}
if(i>=1 && dp[i-1][j] && j+stones[i] <=scale)
{
dp[i][j+stones[i]] = 1;
if(fabs(sum - j - stones[i] - j - stones[i]) < min) min = fabs(sum - j - stones[i] - j - stones[i]);
}
}
}
return min;
}

相关推荐