题解 | #剪绳子#

贪心需要数学定理，证明不了。。。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int cutRope(int n) {
      //  贪心
      if (n <= 3) {
        return n - 1;
      }
      int res = 1;
      //  余下情况为 2 3 4，4 由 1 和 3 组成，分成 2 2 更大
      while (n > 4) {
        res *= 3;
        n -= 3;
      } 
      
      return res * n;
    }
};

dp比较直观理解

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int cutRope(int n) {
      if (n <= 3) {
        return n - 1;
      }
      
      std::vector<int> dp(n + 1, -1);
      dp[1] = 1;
      dp[2] = 2;
      dp[3] = 3;
      
      for (int i = 4; i <= n; ++i) {
        for (int j = 1; j <= i / 2; ++j) {
          dp[i] = std::max(dp[i], j * dp[i - j]);
        }
      }
      
      return dp[n];
    }
};