绳子"/>
割绳子
题目描述
给你一根长度为n的绳子,请把绳子剪成整数长的m段(m、n都是整数,n>1并且m>1),每段绳子的长度记为k[0],k[1],…,k[m]。请问k[0]xk[1]x…xk[m]可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。
输入描述: 输入一个数n,意义见题面。(2 <= n <= 60)
输出描述: 输出答案。
示例
输入 8
输出 18
<?phpfunction cutRope($number)
{// write code here$arr[0] = 0;$arr[1] = 1;$arr[2] = 2;$arr[3] = 3;if ($number < 2){return 0;}if ($number < 4){return $arr[$number-1];}for($i = 4; $i <= $number; $i++){$max = 0;for($j = 1; $j <= $number/2; $j++){$t = $arr[$j] * $arr[$i-$j];if ($t > $max) {$max = $t;}}$arr[$i] = $max;}return $arr[$number];
}
go
package mainimport ("fmt"
)func main() {fmt.Println(gsz(5))
}func gsz(num int) int {arr := make([]int, 0)for i := 0; i < 4; i++ {arr = append(arr, i)}if num < 2 {return 0}if num < 4 {return arr[num-1]}for i := 4; i <= num; i++ {max := 0for j := 1; j <= num/2; j++ {t := arr[j] * arr[i-j]if t > max {max = t}}arr = append(arr, max)}return arr[num]
}
更多推荐
割绳子
发布评论