刷题《剑指Offer》day05

题目来源：力扣《剑指Offer》第二版
完成时间：2022/07/26

• • 14- I. 剪绳子
  • • 我的题解
  • 14- II. 剪绳子 II
  • • 我的题解

这题用dp的思路求解即可

class Solution {
public:
    int max = 0;

    int cuttingRope(int n) {
        if(n == 2) return 1;
        if(n == 3) return 2;
        vector product(n+3);
        product[0] = 0;
        product[1] = 1;
        product[2] = 2;
        product[3] = 3;

        for(int i = 4;i <= n;i++){
            max = 0;
            for(int j = 1;j <= i/2;j++) {
                int num = product[i - j] * product[j];
                if(num > max){
                    max = num;
                }
                product[i] = max;
            }
        }
        return product[n];
    }
};

注意这道题的范围变了，如果再用动态规划的思路会出现溢出。这道题的思路就是尽量把绳子长度大于5时拆分成3（数学不好，证明略）。

class Solution {
public:

    int cuttingRope(int n) {
        if(n == 2) return 1;
        if(n == 3) return 2;
        if(n == 4) return 4;

        long result = 1;
        while(n > 4){
            result = (result * 3) % 1000000007;
            n-=3;
        }
        result = (result * n) % 1000000007;
        return (int)result;
    }
};