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];
}