剑指 Offer 14- I. 剪绳子

文章目录

• 题目描述
• 方法一：动态规划
• • 思路
  • 代码
• 方法二：数学推导
• • 思路
  • 代码

题目描述

方法一：动态规划

思路

1. 定义一个一维数组 dp，dp[i] 表示 长度为 i 的绳子所有分段方式中各段乘积的最大值；
2. 由于绳长和所分段数都是整数且大于1，所以初始化 dp[2] = 1；
3. 对于长度为 i 的绳子，第一段可分的长度为 1 至 i - 1，由于 1 对于最终各段的乘积没有贡献，所以可分段为 2 至 i - 1，若第一段被分的长度为 j （1 < j < i）,则其各段乘积最大值要么是分为两段的 j * (i - j)，要么是被分为多段 j * dp[i - j]。

代码

class Solution {
public:
    int cuttingRope(int n) {
        vector<int> dp(n + 1, 0);
        dp[2] = 1;
        for (int i = 3; i < n + 1; ++i) {
            for (int j = 2; j < i; ++j) {
                dp[i] = max(dp[i], j * (i - j), j * dp[i - j]);
            }
        }
        return dp[n];
    }
private:
    int max(int a, int b, int c) {
        return a > b ? (a > c ? a : c) : (b > c ? b : c);
    }
};
           

方法二：数学推导

思路

具体思路还是看大佬的推导吧：

面试题14- I. 剪绳子（数学推导 / 贪心思想，清晰图解）

代码

class Solution {
public:
    int cuttingRope(int n) {
        if (n <= 3) {
            return n - 1;
        }
        int res = pow(3, n / 3);
        if (n % 3 == 2) { // 最后只剩长度为 2 的段
            res *= 2;
        }
        else if (n % 3 == 1) { // 最后剩的是长度为 1 的段，和一个长度为 3 的合在一起为 4，这是多乘了一个 3，所以除去
            res = res / 3 * 4;
        }
        return res;
    }
};