题解 | #剪绳子#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int cutRope(int n ) {
    // write code here
    if(n<4){
        return n==3?2:1;
    }
    int* dp=(int*)calloc(n+1,sizeof(int));//初始化dp数组，记录当前长度的最大返回值
    dp[1]=1;dp[2]=2;dp[3]=3;//不能再划分子段的绳子最大长度
    for(int i=4;i<=n;i++){
        for(int j=1;j<i;j++){
            if(dp[i]<j*dp[i-j]){
                dp[i]=j*dp[i-j];
            }
        }
    }
    n=dp[n];free(dp);
    return n;
}