JZ67 剪绳子

本文最后更新于：2022年4月9日 中午

image-20211010160530563

Solution

  • 动态规划

对长度为i的绳子, 在j处的切割后, 接下来有两种选择:

  1. 继续切(i - j)长度的绳子, 则 ans = dp[i - j] * j
  2. 不切了, 则 ans = (i - j) * j
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int cutRope(int number) {
        if (number <= 0) return 0;
        vector<int> dp (number+1, 0);    // dp[i] 表示长度为 i 的最大乘积

        dp[2] = 1;  // 只能分成两段 1x1=1
        for (int i = 3; i < number+1; ++i) {
            for (int j = 1; j < i; ++j) {
                dp[i] = max(dp[i], max(j * (i-j), j * dp[i-j]));
            }
        }
        return dp[number];
    }
};