🌕🌗 剑指 Offer 14- I. 剪绳子

难度: 🌕🌗

问题描述

---

解法 1 - 经验公式

class Solution {
    public int cuttingRope(int n) {
        // 思路：
        // 经验公式，尽可能分为 3 的长度
        if(n == 2) {
            return 1;
        }
        if(n == 3) {
            return 2;
        }
        int count = n / 3;
        int lef = n % 3;
        if(lef == 0) {
            return (int)Math.pow(3, count);
        } else if(lef == 1) {
            return (int)Math.pow(3, count - 1) * 4;
        } else {
            return (int)Math.pow(3, count) * 2;
        }
    }
}

---

输出 1

---

解法 2 - dp

class Solution {
    public int cuttingRope(int n) {
        // 思路：
        // dp[i] - 将长度 i 的绳子分成多段能够形成的最大长度
        // 如果尝试对 dp[i] 进行切分 2 段，那么左半最大长度为 max{dp[k], k}，右半段同理
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for(int i = 2; i <= n; i ++) {
            // j - 左半段的长度，最大长度为总区间的一半，再大了就和之前的重复了
            for(int j = 1; j <= i / 2; j ++) {
                dp[i] = Math.max(dp[i], Math.max(dp[j], j) * Math.max(dp[i - j], i - j));
            }
        }
        return dp[n];
    }
}

---

输出 2