剪绳子(合集)

剪绳子I

• 剪绳子I

int cuttingBamboo(int bamboo_len) {
    vector<int> dp(bamboo_len + 1, 0);
    dp[1] = 1;
    for (int i = 2; i <= bamboo_len; i++) {
        for (int j = 1; j <= i/2; j++) {
            // 固定j, 然后考虑 i-j 是否需要继续拆分
            int max_value = max(j*(i-j), j*dp[i-j]);
            dp[i] = max(dp[i], max_value);
        }
    }
    return dp[bamboo_len];
}

剪绳子II

• 剪绳子II

// 真难，需要理解快速幂求余，感觉面试不会考察，先跳过了。
int cuttingBamboo(int bamboo_len) {
    if (bamboo_len < 4) return bamboo_len - 1;
    static const int MAX_VALUE = 1e9+7;
    int b = bamboo_len % 3;
    long rem = 1, x = 3;
    for (int a = bamboo_len/3 -1; a > 0; a /= 2) {
        if (a%2 == 1) rem = (rem * x) % MAX_VALUE;
        x = (x * x) % MAX_VALUE;
    }

    if (b == 0) return (int)(rem * 3 % MAX_VALUE);
    if (b == 1) return (int)(rem * 4 % MAX_VALUE);

    return (int)(rem * 6 % MAX_VALUE);
}