C语言求解 剪绳子

解题思路

动态规划问题,假如一段绳子为n=10米,那么将这段绳子看成两部分,可能的切割位置在 1~9这9个位置之间,因此求一个最大值,dp[10]=max(1*dp[9],2*dp[8],3*dp[7]......9*dp[1]),因此正向计算,dp[1]=1,dp[2]=2,dp[3]=3,dp[4]=4,从而递推dp[5]...dp[n]。

由于绳子必须剪一刀,因此n=2 返回1,n=3 返回2,n=4 返回4。

 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @return int整型
 *
 * C语言声明定义全局变量请加上static,防止重复定义
 */
int max(int a,int b){
    if(a>b)
        return a;
    else return b;
}
int cutRope(int n ) {
    if(n<4)
        return n-1;
    int dp[60]={0};
    dp[1]=1;
    dp[2]=2;
    dp[3]=3;
    dp[4]=4;
    int tempmax=0;
    for(int i=5;i<=n;i++){
        tempmax=0;
        for(int j=1;j<i;j++)
            tempmax=max(tempmax,j*dp[i-j]);
        dp[i]=tempmax;
    }
    return dp[n];
}