Leetcode1547：切棍子的最小成本

题目描述：

有一根长度为 n 个单位的木棍，棍上从 0 到 n 标记了若干位置。例如，长度为 6 的棍子可以标记如下：

请参阅第一个示例以获得更直观的解释。
返回切棍子的最小总成本。

代码思路：

这段代码是用来解决一个关于切割木棒的最小成本问题。给定一根长度为 n 的木棒和若干个切割点 cuts，要求将这些切割点排序后，通过若干次切割将木棒分成若干段，每次切割的成本等于切割位置两侧木棒长度的较大值（这里简化为直接计算切割后每段木棒的长度之和，因为每次切割的成本与切割位置两侧木棒长度的较大值相关，但在这个问题中，我们直接累加每段木棒的长度作为总成本的一个简化处理）。目标是找到一种切割方案，使得所有切割的总成本最小。

以下是代码的详细思路：

总结：这段代码通过动态规划解决了给定切割点情况下，将木棒切割成若干段的最小成本问题。通过排序切割点、初始化动态规划数组、逐步计算并更新最小成本，最终得到了整个问题的解。

代码实现：

int cmp(const void*a,const void*b){
    return *(int*)a-*(int*)b;
}
int minCost(int n, int* cuts, int cutsSize){
    int* ncut=(int*)malloc(sizeof(int)*(cutsSize+2));
    for(int i=0;i<cutsSize;i++){
        ncut[i]=cuts[i];
    }
    ncut[cutsSize]=0;
    ncut[cutsSize+1]=n;
    qsort(ncut,cutsSize+2,sizeof(int),cmp);
    int len=cutsSize+2;
    int** dp=(int**)malloc(sizeof(int*)*(len));
    for(int i=0;i<len;i++){
        dp[i]=(int*)malloc(sizeof(int)*len);
        memset(dp[i],0,sizeof(int)*len);
    }
    for(int i=0;i<len-2;i++){
        dp[i][i+2]=ncut[i+2]-ncut[i];
    }
    for(int k=3;k<len;k++){
        for(int i=0;i<len-k;i++){
            for(int j=i+1;j<i+k;j++){
                int tmp=dp[i][j]+dp[j][i+k]+ncut[i+k]-ncut[i];
                if(dp[i][i+k]==0)
                    dp[i][i+k]=tmp;
                else  dp[i][i+k]=fmin(dp[i][i+k],tmp);
            }
        }
    }
    return dp[0][len-1];
}