Sword finger offer 14- I. cut rope

Original link ： The finger of the sword Offer 14- I. Cut the rope

solution:

        Dynamic programming ：

State means :dp[i] The length is i The maximum value of the product after the rope is segmented
The length is i The rope of can be reduced to j and i - j Two paragraphs , This can be divided into two cases ：

① i - j No further reduction , therefore dp[i] = max(dp[i], j * (i - j));
② i - j Continue to reduce , therefore dp[i] = max(dp[i], j * dp[i - j]);

So it is concluded that Transfer equation ：

        dp[i] = max(dp[i], j * max(dp[i - j], i - j)); 

class Solution {
public:
    int cuttingRope(int n) {
        if(n == 2) return 1;    
        if(n == 3) return 2;    

        vector<int> dp(n + 1);  //dp[i] The length is i The maximum value of the product of each section after the rope is cut 
    
        for(int i = 1;i <= n;i++) {
            for(int j = 1;j < i;j++) {
                dp[i] = max(dp[i], j * max(dp[i - j], i - j));    // Transfer equation 
            }
        }
        return dp[n];
    }
};

  greedy ：

        Reduce the length as much as possible to 3 The rope of .

class Solution {
public:
    int cuttingRope(int n) {
        if(n <= 3) return n - 1;   // A special case 

        int res = 1;
        while(n > 4) {
            res *= 3;
            n -= 3;
        }
        return res * n;
    }
};