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