剑指 Offer 14- I. 剪绳子

剑指 Offer 14- I. 剪绳子

https://leetcode-cn.com/problems/jian-sheng-zi-lcof/

动态规划，dp[i] 表示长度为 i 的绳子能产生出来的最大乘积（这一段绳子可能剪了多次，也可能一次都没剪），因为题目至少要求剪一刀，因此再剪了一刀后，剩余的绳子可以不剪，这是为了方便状态转移。

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
30
31
func cuttingRope(n int) int {
    // special case
    if n == 2 {
        return 1
    }
    if n == 3 {
        return 2
    }

    dp := make([]int, n+1)
    // 剩余绳子的最大长度
    dp[1] = 1
    dp[2] = 2
    dp[3] = 3

    for length := 4; length <= n; length++ {
        // 剪掉长度为 cutted 的一段，求出剪掉多长能取到最大值
        for cutted := 1; cutted < length; cutted++ {
            dp[length] = max(dp[length],  dp[length-cutted] * dp[cutted])
        }
    }

    return dp[n]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}