剑指 Offer 14- I. 剪绳子

原题链接：剑指 Offer 14- I. 剪绳子

solution:

        动态规划：

状态表示:dp[i]表示长度为i的绳子分段后乘积的最大值
长度为i的绳子可以减成 j 和 i - j两段,此时可以分成两种情况：

① i - j 不继续减,因此dp[i] = max(dp[i], j * (i - j));
② i - j 继续减,因此dp[i] = max(dp[i], j * dp[i - j]);

因此得出转移方程：

        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]表示长度为i的绳子剪完后各段乘积的最大值
    
        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));    //转移方程
            }
        }
        return dp[n];
    }
};

  贪心：

        尽可能多的减长度为3的绳子。

class Solution {
public:
    int cuttingRope(int n) {
        if(n <= 3) return n - 1;   //特殊情况

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