描述

示例

思路

这道题为动态规划相关题目，动态规划相关知识见知乎动态规划

一旦分出一段长度为1的小段，只会减少总长度，还不能增加乘积，因此长度为2的绳子不分比分开的乘积大，长度为3的绳子不分比分开的乘积大，长度为4的绳子分成2*2比较大。前面的我们都可以通过这样递推得到，后面的呢？ 同样递推！如果我有一个长度为n的绳子，我们要怎么确定其分出最大的乘积，我们可以尝试其中一段不可分的为j，那么如果另一段n−j最大乘积已知，我们可以遍历所有j找到这个最大乘积。因此用dp[i]表示长度为i的绳子可以被剪出来的最大乘积，那么后续遍历每个j的时候，我们取最大p[i]=max(dp[i],j∗dp[i−j])就好了。

具体做法

• 检查当number不超过3的时候直接计算。
• 用dp数组表示长度为i的绳子可以被剪出来的最大乘积，初始化前面4个容易推断的。
• 遍历每个长度，对于每个长度的最大乘积，可以遍历从1到i的每个固定一段，按照上述公式求的最大值。
• 最后数组最后一位就是答案。

代码

#include <algorithm>
#include<vector>
using namespace std;
class Solution {
  public:
    int cutRope(int n) {
        if (n < 2 || n > 60) return -1;
        if (n == 3 || n == 2) return n - 1;
        vector<int> dp(n + 1, 0);
        dp[1] = 1;
        dp[2] = 2;   //n若为2，因为m>1,则dp为1，n大于3时长度为2可以不切，则dp为2
        dp[3] = 3;
        dp[4] = 4;
        //遍历后续每一个长度
        for (int i = 5; i <= n; i++)
            //可以被分成两份
            for (int j = 1; j < i; j++)
                //取最大值
                dp[i] = max(dp[i], j * dp[i - j]);
        return dp[n];
    }
};