1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

// @Title: 剪绳子 (剪绳子  LCOF)
// @Author: 15816537946@163.com
// @Date: 2022-02-23 13:47:50
// @Runtime: 0 ms
// @Memory: 1.9 MB
func cuttingRope(n int) int {
	dp := make(map[int]int)
	dp[1] = 1 // 首项
	for i := 2; i < n+1; i++ {
		j, k := 1, i-1
		res := 0
		for j <= k {
			res = max(res, max(j, dp[j])*max(k, dp[k])) // 递推公式
			j++
			k--
		}
		dp[i] = res
	}
	return dp[n]
}

func max(i int, j int) int {
	if i > j {
		return i
	}
	return j
}